Recursion replaces loops

Base case first

There are no loops, so repetition is a function that calls itself. Every such function needs a case that stops, written first so the reader sees it immediately:

factorial :: Integer -> Integer factorial 0 = 1 factorial n = n * factorial (n - 1) -- factorial 5 == 120

The second equation calls the same function with a smaller argument. GHC evaluates it until the base case answers, then multiplies back up the stack.

Structural recursion

Most recursion follows the shape of the data instead of a counter. For a list, the two cases are the empty list and a cons:

myLength :: [a] -> Int myLength [] = 0 myLength (_:xs) = 1 + myLength xs myReverse :: [a] -> [a] myReverse [] = [] myReverse (x:xs) = myReverse xs ++ [x]

The second function is correct and quadratic, because ++ copies the left list at every step. The next section fixes it with an accumulator.

Accumulators

An accumulator carries the result built so far. The recursive call gets a bigger accumulator, and the base case returns it unchanged:

reverseFast :: [a] -> [a] reverseFast xs = go [] xs where go acc [] = acc go acc (y:ys) = go (y:acc) ys

The helper is hidden in a where block, so the public function keeps a clean one-argument signature. This pattern appears everywhere in real code, and the fold functions of lesson 18 generalise it.

Trust the recursion

The mental trick is to assume the recursive call already returns the right answer for the smaller input, then check only the step. Here is a tree-free example that sums the squares of a list:

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

If the tail already gives the sum of its squares, adding the square of the head is obviously right, and the empty list is obviously zero. That is the whole proof.

Next: map, filter, and foldr

Article author: Arthur Isaev