Recursion in Haskell

Analogy categoryAnalogies

Why Haskell Uses Recursion Instead of Loops

Haskell has no for or while loop construct because looping inherently relies on mutable counters and accumulators, which conflicts with the language's commitment to immutability — so recursion, where a function calls itself with a smaller version of the problem, is the natural replacement. A recursive function needs at least one base case that stops the recursion, like factorial 0 = 1, and at least one recursive case that reduces the problem and calls itself, like factorial n = n * factorial (n - 1), and if you omit the base case, the function will recurse forever until it exhausts the stack. Recursion in Haskell isn't a fallback pattern used only when convenient — it's the idiomatic way to express repetition, and the standard library's higher-order functions (map, filter, foldr) are themselves implemented using recursion under the hood.

🏏

Cricket analogy: Recursion is like commentating an innings ball by ball: describe the current delivery, then recursively call 'commentate the next ball' until you hit the base case of the last ball of the innings, rather than a for-loop over overs.

Structural Recursion on Lists

The most common recursion pattern in Haskell walks a list structurally, matching [] as the base case and (x:xs) as the recursive case, as in myLength [] = 0 and myLength (x:xs) = 1 + myLength xs, which mirrors exactly how the list itself is built up from : and []. This structural symmetry is why list recursion in Haskell feels natural rather than error-prone — the shape of your recursive function's pattern match echoes the shape of the data type's constructors, so functions like myLength, mySum, and myReverse all follow the same template. When the recursive call isn't in the last position (myReverse (x:xs) = myReverse xs ++ [x] calls ++ after the recursive call returns), each pending call adds a frame that must be resolved on the way back out, whereas placing an accumulator parameter first, as in go acc [] = acc; go acc (x:xs) = go (x:acc) acc, avoids growing that call structure.

🏏

Cricket analogy: Recursing over a list of deliveries — process this ball, then recurse on the rest of the over — mirrors how an over itself is built delivery by delivery, so the recursive commentary naturally matches the over's structure.

haskell

-- Non-tail recursion: builds up work before combining
myLength :: [a] -> Int
myLength [] = 0
myLength (_:xs) = 1 + myLength xs

-- Accumulator-based (tail-recursive) version
myLengthAcc :: [a] -> Int
myLengthAcc xs = go 0 xs
  where
    go acc []     = acc
    go acc (_:ys) = go (acc + 1) ys

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

Laziness, Accumulators, and Infinite Structures

Because Haskell is lazy, an accumulator-based recursive function like go acc (x:xs) = go (x + acc) xs doesn't automatically avoid stack problems the way it would in a strict language — the acc parameter can build up a chain of unevaluated additions (a 'thunk') that only gets forced at the very end, sometimes causing a stack overflow despite looking tail-recursive; using foldl' from Data.List, which forces the accumulator at each step, is the idiomatic fix. Laziness also has a major upside: recursive definitions can describe genuinely infinite structures, like ones = 1 : ones or fibs = 0 : 1 : zipWith (+) fibs (tail fibs), and consumers like take 10 fibs only force as many list cells as they actually need, so the infinite recursive definition never tries to compute an infinite value all at once.

🏏

Cricket analogy: Laziness is like a scorer who only writes down a boundary's run total when asked for the scorecard, rather than tallying after every single ball — you can query 'runs after over 10' and only that much gets computed, no more.

The where clause is a common place to define a tail-recursive helper with an accumulator, keeping the accumulator hidden from the function's public type signature — e.g. myLengthAcc xs = go 0 xs where go acc [] = acc; go acc (_:ys) = go (acc+1) ys exposes only myLengthAcc :: [a] -> Int to callers.

Don't assume an accumulator automatically makes recursion efficient in Haskell the way it does in strict languages — unevaluated thunks in a lazy accumulator can still overflow the stack. Use foldl' (strict left fold, from Data.List) instead of foldl when you want guaranteed strict, memory-efficient accumulation.

Haskell has no for/while loops; recursion is the idiomatic replacement for repetition.
A recursive function needs a base case (stops recursion) and a recursive case (progresses toward it).
List recursion typically mirrors list construction: [] as base case, (x:xs) as recursive case.
Non-tail recursive calls (like myReverse) build up pending work resolved after the recursive call returns.
Accumulator-passing style can enable tail recursion but doesn't guarantee stack safety under laziness.
foldl' from Data.List forces the accumulator strictly, avoiding thunk buildup that foldl allows.
Laziness enables genuinely infinite recursive definitions, like fibs, where only needed elements are computed.