A-Level · Recursion

Recursion Fundamentals

Recursion trips people up for one specific reason: it's genuinely hard to hold "a function calling itself, five layers deep, all still waiting" in your head at once. So don't hold it in your head, watch it happen. Every call, every wait, every return, one at a time, below.

Section 2

Factorial: calls stack up, then unwind

factorial(5) doesn't compute anything by itself. It calls factorial(4) and waits. factorial(4) calls factorial(3) and waits. This keeps going until factorial(1) finally has a real answer, and only then does anything actually get multiplied, on the way back up.

factorial(5)
Ready. Press Step to begin calling factorial(5).

The code being run

Controls

Exam tips

  • Every recursive function needs a base case (here, n ≤ 1) that stops the calls, and a recursive case that makes progress toward it (here, n-1 each time).
  • Nothing is actually multiplied until the base case returns, the whole chain of calls is just "on hold" waiting for an answer to appear from below.
Section 3

What's actually inside a stack frame

Each of those boxes above is a real thing called a stack frame, and it holds specific information, not just "the function is running". Same factorial(5), same bottom-up stack, this time with every field labelled.

Controls

Every frame stores

  • Parameters: the value of n for this specific call
  • Local variables: anything declared inside this call (none needed here, but often present)
  • Return address: exactly which line to resume once this call finishes, so control goes back to the right place
  • Return value: filled in only once this frame actually completes

Exam tips

  • This is exactly why deep recursion can cause a stack overflow: every call, however small, needs a real frame of memory, and there's a limit to how many can exist at once.
  • An iterative version of factorial needs only one set of variables, reused each loop, recursion needs a brand new frame for every single call, still waiting, until the base case is hit.
Section 4

Fibonacci: recursion that branches, and the trap that creates

Factorial's calls form a single chain. Fibonacci's calls form a tree: computing fib(5) means calling fib(4) and fib(3), and each of those calls two more. Every circle below is one call, the number inside is which fib(N) that call is computing. Step through and watch for something specific: the exact same call appearing more than once.

being called right now resolved, value shown below it base case (fib(0) or fib(1))
Ready. Press Step to build the call tree for fib(5), one call at a time.

Controls

Calls so far

0

The blowup, in real numbers

fib(2) alone gets computed independently 3 separate times just within fib(5). By fib(30), that same sub-problem gets recomputed over half a million times, every single one recalculating something already solved moments earlier.

Exam tips

  • This is what an exponential time complexity actually looks like in practice, not just a phrase in a textbook: the work roughly doubles for every one step n increases, which is why fib(30) is fine but fib(50) can take minutes.
  • The problem isn't recursion itself, it's repeated work on identical sub-problems. Factorial never had this issue, because its calls form a single chain with no repeats.
Section 5

Memoisation: remember, don't recompute

Same fib(5), same tree shape, same circles meaning the same thing as above, but this time, the moment a value has already been calculated once, it's simply looked up instead of recalculated. Watch entire branches get skipped in a single step.

resolved normally cache hit, no recomputation, no further calls below it
Ready. Press Step to build fib(5) again, this time with a cache.

Controls

Calls so far

0

Cache contents

Naive vs memoised, side by side

Exam tips

  • Memoisation trades memory for speed: the cache has to store every result computed so far, but each one is only ever computed once.
  • This turns fib(n) from exponential time down to linear time, roughly n calls instead of roughly 2n, purely by refusing to solve the same sub-problem twice.
  • This general technique, breaking a problem into overlapping sub-problems and caching results, is called dynamic programming.
Section 6

Check your understanding