Recursion

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 a 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, as shown in the following code:

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 in on itself:

-- 2 + sumNonTail [3, 5, 7]
-- 2 + (3 + sumNonTail [5, 7])
-- 2 + (3 + (5 + sumNonTail [7]))
-- 2 + (3 + (5 + (7 + sumNonTail [])))
-- 2 + (3 + (5 + (7 + 0)))
-- 2 + (3 + (5 + 7))
-- 2 + (3 + 12)
-- 2 + 15
-- 17

The sumNonTail function is non-tail-recursive. Because the recursion is "trapped" by the + operator, we need to hold the entire list in memory to perform the sum.

Tail recursion

Tail recursion addresses the exorbitant use of space we have with non-tail-recursive processes:

sumTail' acc [] = acc
sumTail' acc (x:xs) = sumTail' (acc + x) xs
sumTail xs = sumTail' 0 xs

This form of recursion looks less like mathematical induction than the sumNonTail function did, and it also requires a helper function sumTail' to get the same ease of use that we had with sumNonTail. The advantage is clear when we look at the use of "constant space" in this process:

-- sumTail [2, 3, 5, 7]
-- sumTail' 0 [2, 3, 5, 7]
-- sumTail' 2 [3, 5, 7]
-- sumTail' 5 [5, 7]
-- sumTail' 10 [7]
-- sumTail' 17 []
-- 17

Even though sumTail is a recursive function, it expresses an iterative process. sumNonTail is a recursive function that expresses a recursive process.

Folding abstracts recursion

Tail recursion is captured by the foldl function, as shown in the following code:

  foldlSum = foldl (+) 0

The foldl function expands in exactly the same way as sumTail'. In contrast, foldrSum expands in the same way as sumNonTail:

foldrSum = foldr (+) 0

One can clearly see the tail recursion in the definition of foldl, whereas in the definition of foldr, recursion is "trapped" by f:

foldr _ v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

foldl _ v [] = v
foldl f v (x:xs) = foldl f (f v x) xs