Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 57 ยท Functions

Recursion

Learn recursion in Haskell: base and recursive cases, accumulators, tail recursion, and how laziness and strictness affect stack and memory use.

Haskell has no for or while loops. Anything you would repeat with a loop, you express either with a library function like map and foldr, or with a function that calls itself. That second approach is recursion, and it is the foundation under the library functions as well.

This lesson shows how to design a recursive function, how an accumulator turns a slow recursion into a fast one, what tail recursion means in a lazy language, and where recursion can still cost memory. It builds on pattern matching and guards.

GHC is not installed on this site, so the Haskell code blocks are read-only. The runnable editors are JavaScript stand-ins that follow the same structure. JavaScript does not optimise tail calls, so the stand-ins use small tricks, described where they appear.

Two parts of every recursion

A recursive function needs:

  1. A base case: an input simple enough to answer directly.
  2. A recursive case: a step that reduces the problem and calls the function on the smaller problem.
HASKELL
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

factorial 3 unfolds like this:

HASKELL
factorial 3
= 3 * factorial 2
= 3 * (2 * factorial 1)
= 3 * (2 * (1 * factorial 0))
= 3 * (2 * (1 * 1))
= 6

If you forget the base case, or the recursive call does not get closer to it, the function never finishes. With factorial (-1) the argument just keeps going down, so the program runs until memory is exhausted. Using a guard | n < 0 = error "negative" or choosing an unsigned-style type is a way to prevent that.

Recursion over lists

Lists are the natural data for recursion, because a list is either empty or a head and a tail. Match on both shapes, handle [] as the base case, and recurse on the tail.

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

myMaximum :: [Int] -> Int
myMaximum []       = error "myMaximum: empty list"
myMaximum [x]      = x
myMaximum (x : xs) = max x (myMaximum xs)

myMap :: (a -> b) -> [a] -> [b]
myMap _ []       = []
myMap f (x : xs) = f x : myMap f xs

myMap is, nearly word for word, how the Prelude's map works. Seeing that is the key insight of this lesson: higher-order functions like map, filter and the folds in Higher-Order Functions are recursion patterns somebody already wrote and named.

Thinking about it

When designing a list recursion, ask two questions: "What is the answer for the empty list?" and "If I already had the answer for the tail, how would I get the answer for the whole list?" You do not need to trace every call. Trust the recursive call to work, and write the step that combines the head with its result.

Designing a recursion

Base case The smallest input has a direct answer.
Recursive case Call yourself on something smaller.
Combine Merge the head with the recursive answer.

Trust the call on the smaller problem. Do not trace it by hand.

1 / 2

Accumulators

Naive recursion can be slow. The textbook example is the Fibonacci sequence:

HASKELL
fib :: Int -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

This is correct but recomputes the same values again and again. fib 30 makes over two million calls, and the count grows exponentially.

An accumulator is an extra argument that carries the work done so far. A helper function usually holds it, so callers keep the simple signature.

HASKELL
fibFast :: Int -> Integer
fibFast n = go n 0 1
  where
    go 0 a _ = a
    go k a b = go (k - 1) b (a + b)

The helper go k a b keeps the two most recent Fibonacci numbers in a and b. Each step moves forward one position, so fibFast n takes about n steps instead of exponentially many. The name go is a common convention for such a helper.

Accumulators also fix list functions. A naive reverse using ++ is quadratic, because each append copies the growing left list. The accumulator version builds the answer with the cheap cons operator:

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

Tail recursion

A call is a tail call when it is the very last thing a function does, with nothing left to do with its result. go (k - 1) b (a + b) is a tail call. n * factorial (n - 1) is not, because after the recursive call returns, the multiplication still has to happen.

In many languages the distinction matters for the stack, because each non-tail call waits on the stack for its result. In Haskell it matters less than you might expect, for two reasons:

  • GHC compiles tail calls into jumps, so a tail-recursive loop does not grow the stack.
  • GHC's run-time stack is allowed to grow very large by default, so deep non-tail recursion like mySum on a long list works fine for ordinary sizes, using memory instead of crashing early.

So write the clearest version first. Many simple Haskell recursions that look like they use the stack are fine, and the Prelude's map and ++ use the "guarded" form f x : map f xs, which works lazily and in constant space as the consumer pulls elements.

Strictness and the lazy accumulator trap

There is a catch with accumulators. Haskell is lazy, so the argument acc + x is not computed when the call happens. It is stored as an unevaluated thunk until someone needs it.

HASKELL
sumTo :: Int -> Int
sumTo n = go n 0
  where
    go 0 acc = acc
    go k acc = go (k - 1) (acc + k)

Without optimisation, acc can grow into a chain of a million unevaluated additions, (((0 + 1) + 2) + 3) ..., which is only collapsed at the very end. This costs a lot of memory, and is a classic space leak. With -O, GHC's strictness analysis usually notices that acc is always needed and evaluates it eagerly, so the problem disappears in compiled code, but you should not rely on that for more complex functions.

The explicit fix is to force the accumulator at each step with a bang pattern:

HASKELL
# LANGUAGE BangPatterns #

sumTo :: Int -> Int
sumTo n = go n 0
  where
    go 0 !acc = acc
    go k !acc = go (k - 1) (acc + k)

The ! tells GHC to evaluate acc before continuing. The topic gets a whole lesson in Strictness, Bang Patterns and seq, and the library function foldl' does the same job for folds.

Mutual recursion and local helpers

Two functions may call each other, as long as they live in the same scope:

HASKELL
isEven, isOdd :: Int -> Bool
isEven 0 = True
isEven n = isOdd (n - 1)

isOdd 0 = False
isOdd n = isEven (n - 1)

This is a toy example (just use even), but mutual recursion shows up in parsers and evaluators. Prefer small local helpers in a where block to keep accumulator arguments out of your public function's type.

Running the ideas

The stand-ins below use JavaScript. They follow the Haskell structure, but JavaScript lacks guaranteed tail-call optimisation, so a loop replaces the tail call where needed. The first one counts calls to show why the accumulator helps.

JS Naive recursion vs accumulator

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The call counts show the exponential growth: each increase of 5 in n multiplies the work by roughly eleven.

The second stand-in uses recursion for lists, copying the shapes of mySum, myMap, myReverse and factorial. Because JavaScript's stack is small, it also shows a trampoline: a tail call returns a function instead of making the call, and a loop keeps running those functions, which keeps the stack flat. Haskell does this for you automatically.

JS List recursion and a trampoline

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The n suffix makes JavaScript BigInt values, which behave like Haskell's unbounded Integer. A plain Int in Haskell would wrap around at 64 bits instead, so factorial 25 :: Int gives a wrong number silently.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What two parts does a well-formed recursive function need?

    The base case ends the recursion, and each recursive call must get closer to it.
  2. 2. Which call is a tail call?

    A tail call is the last action of the function. In the other options something still happens (multiplication, addition, cons) after or around the call.
  3. 3. Why can a recursive helper with an accumulator leak memory in Haskell?

    Laziness delays acc + k until it is needed, so a long loop piles up pending additions. A bang pattern or foldl' forces it step by step.
  4. 4. What does the accumulator do in myReverse xs = go xs []?

    Each element is consed onto acc, so the first element ends up last. The finished answer is returned in the base case.
  5. 5. How is the Prelude's map related to recursion?

    map f (x : xs) = f x : map f xs, with map f [] = []. Higher-order functions package common recursion patterns.

Summary

  • A recursive function has a base case and a recursive case that moves toward it.
  • Recursion over lists matches [] and x : xs; library functions like map are exactly such recursions.
  • An accumulator, usually in a local go helper, can turn exponential or quadratic work into linear work.
  • GHC compiles tail calls into jumps and allows a large stack, so write the clear version first.
  • Lazy accumulators can build thunks; force them with bang patterns or foldl' when a long loop would otherwise leak memory.

Next, see why every Haskell function takes just one argument: Currying and Partial Application.