Recursion | OCR H446

Learning Objectives

By the end of this topic you will be able to:

Define recursion and identify its two essential components

Trace recursive functions and identify the call stack during execution

Write recursive algorithms for factorial, Fibonacci and other problems

Compare recursion with iteration: advantages and disadvantages

Recursion Basics

What is Recursion?

A recursive function is one that calls itself. Every recursive solution must have two essential components:

1. Base case: a condition where the function does NOT call itself — stops the recursion.
2. Recursive case: the function calls itself with a simpler version of the problem — moves toward the base case.

Without a base case, the function calls itself infinitely, eventually causing a stack overflow — the call stack fills up and the program crashes.

Factorial Example

Factorial — Recursive Implementation

function factorial(n):

  if n == 0 then return 1   ← base case

  else return n × factorial(n−1) ← recursive case

Trace: factorial(4)

factorial(4) → 4 × factorial(3)

factorial(3) → 3 × factorial(2)

factorial(2) → 2 × factorial(1)

factorial(1) → 1 × factorial(0)

factorial(0) → 1    ← base case hit

Returns: 1→1→2→6→24

Call Stack

The Call Stack in Recursion

Each time a function calls itself, a new stack frame is pushed onto the call stack containing: the function's local variables, the return address, and the current value of parameters. When the base case is reached, frames are popped in reverse (LIFO) and results are passed back up the chain.

Stack depth = number of recursive calls. For factorial(n), depth = n+1 frames. For large n this can cause a stack overflow — which is why iterative solutions are sometimes preferred for deeply recursive problems.

A stack overflow occurs when the call stack runs out of space due to too many nested recursive calls. This can happen when the base case is incorrect or n is very large.

Recursion vs Iteration

Recursion

Advantages:
• Elegant for naturally recursive problems (trees, BST, quicksort, merge sort)
• Shorter, cleaner code
• Mirrors mathematical definitions

Disadvantages:
• Higher memory use (call stack frames)
• Risk of stack overflow
• Can be slower (function call overhead)

Iteration

Advantages:
• More memory-efficient (no stack frames)
• Faster in practice (no function call overhead)
• No stack overflow risk

Disadvantages:
• Can be more complex code for inherently recursive problems
• May require manual stack management

Exam Practice

OCR H446 Style · 4 marks

The following recursive function is defined: f(n) = 1 if n=1; f(n) = f(n−1) + 2n−1 otherwise. Trace f(4), showing the call stack at each stage. What does this function compute?

[4 marks]

f(4) = f(3)+7. f(3)=f(2)+5. f(2)=f(1)+3. f(1)=1. Unwinding: f(2)=1+3=4. f(3)=4+5=9. f(4)=9+7=16.

Call stack depth reaches 4 frames when f(1) is called; then frames are popped in reverse order returning 1, 4, 9, 16.

The function computes n² (1=1², 4=2², 9=3², 16=4²) — it builds n² by successively adding the next odd number (the pattern 1, 1+3, 4+5, 9+7).

Common Mistakes

Don't Lose Marks

Missing the base case in a recursive solution — every recursive function must have a base case that terminates the recursion. A recursive case alone produces infinite recursion and stack overflow. Always identify and state the base case explicitly in exam answers.

Tracing the recursion in the wrong order — recursive calls go DOWN first until the base case, then results propagate BACK UP. Students often show values being computed during the descent rather than the ascent. The computation happens when frames unwind (are popped), not when they're pushed.

Saying recursion is always better than iteration — OCR questions specifically test understanding of trade-offs. Recursion uses more memory (stack frames) and risks stack overflow. Always mention both advantages and disadvantages when asked to compare.