Recursion in Functional Programming

In a pure functional language there are no loops. There is no for, no while, and no mutable counter to increment — those all depend on changing state, which immutability forbids. So how does a functional program repeat work? Recursion: a function calls itself with smaller or modified arguments until it reaches a stopping point. Recursion is therefore FP's only mechanism for iteration, which makes it one of the most heavily examined ideas in the AQA topic. You must be able to write recursive functions over lists, identify the base and recursive cases, and — above all — trace a recursive call step by step.

---

Spec Mapping

This lesson covers recursion as used in AQA 7517 §4.12.2 (writing functional programs) and connects directly to the general treatment of recursion in §4.1.1. You should be able to: define the base case and recursive case; explain why recursion replaces loops in FP; write and trace recursive list functions using head/tail (x:xs) pattern matching (e.g. length, sum, map); distinguish tail recursion from ordinary recursion and explain its efficiency; and recognise the call-stack cost of deep recursion. It underpins the recursive definitions of map, filter and fold (§4.12.3) and links to divide-and-conquer (§4.3).

Descriptions here are our own restatement of the assessable content rather than a verbatim quotation of AQA's specification.

---

What is Recursion?

Recursion occurs when a function calls itself. Every correct recursive function has two essential parts:

1. Base case(s): the condition(s) under which the function returns a direct answer without calling itself. This is what stops the recursion.
2. Recursive case(s): the condition(s) under which the function calls itself with arguments that are closer to the base case. This is what guarantees progress towards termination.

If you omit the base case, or the recursive case never moves towards it, you get infinite recursion — the functional analogue of an infinite loop, which exhausts the call stack.

Worked example — factorial

The factorial of n (written n!) is defined recursively:

• 0! = 1 — the base case
• n! = n * (n - 1)! — the recursive case

This translates almost word-for-word into Haskell using pattern matching, one equation per case:

factorial :: Int -> Int
factorial 0 = 1                      -- base case
factorial n = n * factorial (n - 1)  -- recursive case

factorial 5    -- 120

def factorial(n):
    if n == 0:            # base case
        return 1
    return n * factorial(n - 1)   # recursive case

Tracing the recursion

Tracing means writing out every step of the call until the base case, then unwinding. This is precisely what AQA asks for, so practise it.

$$\begin{aligned} \mathrm{factorial}\;5 \;&= 5 \times \mathrm{factorial}\;4 \\ &= 5 \times (4 \times \mathrm{factorial}\;3) \\ &= 5 \times (4 \times (3 \times \mathrm{factorial}\;2)) \\ &= 5 \times (4 \times (3 \times (2 \times \mathrm{factorial}\;1))) \\ &= 5 \times (4 \times (3 \times (2 \times (1 \times \mathrm{factorial}\;0)))) \\ &= 5 \times (4 \times (3 \times (2 \times (1 \times 1)))) \\ &= 5 \times (4 \times (3 \times (2 \times 1))) \\ &= 5 \times (4 \times (3 \times 2)) \\ &= 5 \times (4 \times 6) \\ &= 5 \times 24 \\ &= 120 \end{aligned}$$factorial5​=5×factorial4=5×(4×factorial3)=5×(4×(3×factorial2))=5×(4×(3×(2×factorial1)))=5×(4×(3×(2×(1×factorial0))))=5×(4×(3×(2×(1×1))))=5×(4×(3×(2×1)))=5×(4×(3×2))=5×(4×6)=5×24=120​

Notice the two phases: the call winds up (each line adds another pending multiplication) until the base case factorial 0 = 1 is hit, then it unwinds (the multiplications resolve from the innermost outward).

---

Why Recursion Instead of Loops?

An imperative loop relies on a mutable variable:

# Imperative: result is reassigned on every iteration
result = 1
for i in range(1, 6):
    result = result * i     # mutation

In pure functional code, result could never be reassigned. Recursion replaces the loop by carrying the "changing" state in the arguments of each successive call instead of in a mutable cell:

Feature	Loop (imperative)	Recursion (functional)
State management	Mutable counter and accumulator	Arguments carry the state
Termination	Loop condition becomes false	Base case is reached
Repetition	Loop body re-executed	Function re-applied to new arguments
Side effects	Variable mutation	None (pure recursion)

---

Head/Tail List Recursion (the core technique)

Most functional list processing follows one pattern: handle the empty list as the base case, and for a non-empty list split it into its head x and tail xs using the pattern (x:xs), recursing on the tail.

Sum of a list

sumList :: [Int] -> Int
sumList []     = 0                 -- base case: empty list sums to 0
sumList (x:xs) = x + sumList xs    -- recursive case: head + sum of tail

sumList [1, 2, 3, 4, 5]    -- 15

Tracing sumList [1,2,3] shows the pattern clearly:

  sumList [1, 2, 3]
= 1 + sumList [2, 3]       -- x=1, xs=[2,3]
= 1 + (2 + sumList [3])    -- x=2, xs=[3]
= 1 + (2 + (3 + sumList [])) -- x=3, xs=[]
= 1 + (2 + (3 + 0))        -- base case reached
= 1 + (2 + 3)
= 1 + 5
= 6

Length of a list

We do not need the head's value, only its presence, so we discard it with the wildcard _:

lengthList :: [a] -> Int
lengthList []     = 0
lengthList (_:xs) = 1 + lengthList xs

lengthList [10, 20, 30]    -- 3

  lengthList [10, 20, 30]
= 1 + lengthList [20, 30]
= 1 + (1 + lengthList [30])
= 1 + (1 + (1 + lengthList []))
= 1 + (1 + (1 + 0))
= 3

map via recursion

Even the higher-order map is defined by head/tail recursion — apply f to the head, cons it onto the recursively-mapped tail:

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

myMap (*2) [1, 2, 3]
-- = (*2) 1 : myMap (*2) [2, 3]
-- = 2 : ((*2) 2 : myMap (*2) [3])
-- = 2 : (4 : ((*2) 3 : myMap (*2) []))
-- = 2 : (4 : (6 : []))
-- = [2, 4, 6]

This is the crucial connection: the convenient list functions from §4.12.3 are not magic — they are ordinary recursion underneath.

Membership — recursion that may stop early

Not every list recursion processes the whole list. Checking whether a value is present can stop as soon as it is found:

contains :: Int -> [Int] -> Bool
contains _ []     = False                 -- base case: not found in empty list
contains y (x:xs)
    | x == y    = True                    -- found it — stop here
    | otherwise = contains y xs           -- not this one; check the tail

contains 3 [5, 1, 3, 9]    -- True

Trace contains 3 [5, 1, 3, 9]:

  contains 3 [5, 1, 3, 9]
-- 5 /= 3 -> check tail
= contains 3 [1, 3, 9]
-- 1 /= 3 -> check tail
= contains 3 [3, 9]
-- 3 == 3 -> True (the 9 is never examined)
= True

The recursion short-circuits at the first match — a guard returning a base value mid-list is just as valid a stopping point as the empty list.

Maximum — using an element as the base case

To find the largest element we recurse down to a single-element list, then compare on the way back up:

maxList :: [Int] -> Int
maxList [x]    = x                         -- base case: one element is its own max
maxList (x:xs) = max x (maxList xs)        -- larger of head and max-of-tail

maxList [3, 7, 2, 9, 4]    -- 9

  maxList [3, 7, 2, 9, 4]
= max 3 (maxList [7, 2, 9, 4])
= max 3 (max 7 (maxList [2, 9, 4]))
= max 3 (max 7 (max 2 (maxList [9, 4])))
= max 3 (max 7 (max 2 (max 9 (maxList [4]))))
= max 3 (max 7 (max 2 (max 9 4)))     -- base case: maxList [4] = 4
= max 3 (max 7 (max 2 9))
= max 3 (max 7 9)
= max 3 9
= 9

Here the base case is a one-element list rather than the empty list, because the maximum of an empty list is undefined. Choosing the right base case is part of designing a correct recursion.

filter via recursion — a guard decides whether to keep the head

filter is defined by recursion too, but the recursive case uses a guard to decide whether the head is consed onto the result or skipped entirely:

myFilter :: (a -> Bool) -> [a] -> [a]
myFilter _ []     = []                         -- base case
myFilter p (x:xs)
    | p x       = x : myFilter p xs            -- keep head, recurse
    | otherwise = myFilter p xs                -- drop head, recurse

myFilter even [1, 2, 3, 4]

  myFilter even [1, 2, 3, 4]
-- even 1 = False -> drop
= myFilter even [2, 3, 4]
-- even 2 = True  -> keep
= 2 : myFilter even [3, 4]
-- even 3 = False -> drop
= 2 : myFilter even [4]
-- even 4 = True  -> keep
= 2 : (4 : myFilter even [])
= 2 : (4 : [])
= [2, 4]

Where myMap always conses (it transforms every element), myFilter conditionally conses — the only structural difference between the two. Seeing all three of map, filter and length as variations on the same head/tail recursion is the deep insight of this lesson.

Fibonacci — recursion with two recursive calls

fibonacci :: Int -> Int
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)

fibonacci 6    -- 8

Fibonacci has two base cases and two recursive calls. Beware: this naive version is hugely inefficient — it recomputes the same sub-values exponentially many times, giving roughly O(2^n) running time (a classic exam discussion point).

To see why it is so slow, expand fibonacci 5 one level: it needs fibonacci 4 and fibonacci 3; but fibonacci 4 also needs fibonacci 3, so fibonacci 3 is computed twice. One level deeper, fibonacci 2 is computed three times, and the duplication explodes as n grows:

flowchart TD
    F5["fib 5"] --> F4["fib 4"]
    F5 --> F3a["fib 3"]
    F4 --> F3b["fib 3"]
    F4 --> F2a["fib 2"]
    F3a --> F2b["fib 2"]
    F3b --> F2c["fib 2"]

The same fib 3 and fib 2 nodes recur all over the tree — none of the work is shared. An accumulator-based version computes each value once, carrying the previous two results forward, which is O(n):

fibFast :: Int -> Int
fibFast n = go n 0 1
  where
    go 0 a _ = a                    -- a holds fib n when the counter hits 0
    go k a b = go (k - 1) b (a + b) -- slide the window: (a, b) -> (b, a + b)

fibFast 6    -- 8

  go 6 0 1
= go 5 1 1        -- (a,b): (0,1) -> (1, 0+1)
= go 4 1 2        -- (1,1) -> (1, 1+1)
= go 3 2 3        -- (1,2) -> (2, 1+2)
= go 2 3 5        -- (2,3) -> (3, 2+3)
= go 1 5 8        -- (3,5) -> (5, 3+5)
= go 0 8 13       -- (5,8) -> (8, 5+8)
= 8               -- base case returns a

This is a vivid illustration of the misconception that "recursion is slow": the naive recursion is slow because of repeated work, but a well-designed recursion solves the very same problem in linear time. The slowness was never about recursion — it was about the algorithm.

---

Tail Recursion

Tail recursion is a special form in which the recursive call is the very last operation — there is no pending work left to do after it returns.

Ordinary (non-tail) recursion

factorial 0 = 1
factorial n = n * factorial (n - 1)   -- the (n *) multiplication is PENDING until the call returns

Here, after factorial (n - 1) returns we still have to multiply by n. Each pending multiplication occupies a stack frame, so the stack grows with n.

Tail-recursive version (using an accumulator)

factorial :: Int -> Int
factorial n = go n 1
  where
    go 0 acc = acc                    -- base case: answer is in the accumulator
    go k acc = go (k - 1) (k * acc)   -- recursive call is the LAST thing; nothing pending

The running product is carried in the accumulator acc, so when the base case is reached the answer is already computed — there is nothing to unwind. Trace it and note the stack never deepens:

  go 5 1
= go 4 5        -- acc: 1*5 = 5
= go 3 20       -- acc: 5*4 = 20
= go 2 60       -- acc: 20*3 = 60
= go 1 120      -- acc: 60*2 = 120
= go 0 120      -- acc: 120*1 = 120
= 120           -- base case returns acc directly

Why tail recursion matters