Recursion is the loop

There is no loop, only a smaller call

Haskell has no for and no while. To repeat work, a function calls itself on a smaller piece of the problem: the sum of a list is the first value plus the sum of the rest. Because the list keeps getting shorter, the calls eventually run out.

This is called recursion, and it is not an advanced trick here. It is the ordinary way to walk a collection, and every chapter after this one relies on patterns you already know taking care of the walking for you.

The base case is what ends it

A recursive function needs at least one case that answers without calling itself. total [] = 0 answers for the empty list; the other equation handles a list that starts with a value. Two lines describe every list there is, however long.

Without that base case the calls never run out, and the sandbox stops the program after a few seconds. If a program seems to hang, the first thing to look for is a case that should have been written and was not.

where names the pieces

where attaches definitions to the equation above it. The helper it introduces is visible only inside that function, so the rest of the file keeps its own names free. That is where a recursive helper usually goes when the outer function should stay short.

let does the same job inside an expression or a do block: it names values for the lines that follow. Both are there to keep names close to the place where they are used.

A walk and an accumulator

sumOf :: [Int] -> Int
sumOf [] = 0
sumOf (x : xs) = x + sumOf xs

-- The accumulator carries the answer so far.
reverseOf :: [Int] -> [Int] -> [Int]
reverseOf acc [] = acc
reverseOf acc (x : xs) = reverseOf (x : acc) xs

Two places to keep the answer

A recursive function can build its answer on the way back or carry it on the way down. total (x : xs) = x + total xs builds on the way back: nothing is added until the empty list answers, and then the additions unwind in reverse.

An accumulator carries the answer so far in an argument. go k acc = go (k - 1) (acc * k) has the whole answer in acc by the time the base case is reached, so the base case only has to hand it back. Nothing is left to do on the way out.

The choice changes the order. Building on the way back puts the first value in front of an answer that is already finished, which is why countDown answers [5, 4, 3, 2, 1]. The accumulator conses each value as the calls go down, which is why countUp answers [1, 2, 3, 4, 5] from the same numbers.

To see what a recursive function does, substitute rather than guess. Write total [4, 8], replace it with 4 + total [8], then with 4 + (8 + total []), then with 4 + (8 + 0). Each step uses one equation and makes the list shorter, and the last step is the base case. Four lines of substitution explain a function that a paragraph of description only approximates.

Numbers recurse too

The pattern does not need a list. A number counts down to zero the same way a list counts down to [], and the two equations have the same shape: one case that stops, one that does a little work and calls again.

Every call has to move toward the base case. n - 1 and the tail of a list both do; n + 1 and the same list again do not, and the sandbox stops the program when it runs out of patience.

If the number can arrive negative, the base case 0 is not enough, because -1 - 1 never reaches it. Guard with n <= 0 when zero is a floor rather than an exact stop.

Try these next

• Write productOf as a walk over a list, and check it against product for a list of four numbers.
• Change countUp so it answers the same order as countDown, by consing on the way back instead.
• Write repeatText n word that answers the word repeated n times, with n <= 0 answering the empty text.