Recursion is even more fundamental than functions and types, in the sense that we can have recursive functions and types. Moreover, recursion can refer to syntax (a function or type referring to itself) or to the execution process.

Non-tail recursion

Recursion can be viewed as a pattern for avoiding mutable state:

sumNonTail [] = 0
sumNonTail (x:xs) = x + (sumNonTail xs)

Without recursion, we would need to iterate through the list and keep adding to an intermediary sum until the list is exhausted, consider the example:

sumNonTail [2, 3, 5, 7]

This first expands into a nested chain of deferred operations, and when there are only primitives left in the expression, the computation starts folding back on itself:

-- 2 + sumNonTail [3, 5, 7] -- 2 ...

Get Haskell Design Patterns now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.