Recursion

This lesson covers recursion — a fundamental programming technique where a function calls itself. Recursion is a key topic in the OCR A-Level Computer Science (H446) specification and underpins many algorithms and data structures.

---

What is Recursion?

Recursion is a technique where a function calls itself to solve a smaller version of the same problem. Every recursive function has two essential components:

Component	Description
Base case	A condition that stops the recursion (prevents infinite calls).
Recursive case	The function calls itself with a smaller/simpler input.

Analogy

Think of Russian nesting dolls (matryoshka). To find the smallest doll, you open the outer doll (recursive call), then the next, and the next, until you reach a doll that cannot be opened (base case).

---

Structure of a Recursive Function

function solve(problem)
    if problem is simple enough then
        return simple answer          // BASE CASE
    else
        simplify the problem
        return solve(simpler problem)  // RECURSIVE CASE
    endif
endfunction

---

Example 1: Factorial

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

• 0! = 1 (base case)
• n! = n x (n-1)! for n > 0 (recursive case)

Pseudocode (OCR Style)

function factorial(n)
    if n == 0 then
        return 1
    else
        return n * factorial(n - 1)
    endif
endfunction

Python

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))    # Output: 120

Trace

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1 * factorial(0)
= 5 * 4 * 3 * 2 * 1 * 1
= 120

---

Example 2: Fibonacci Sequence

The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

• fib(0) = 0 (base case)
• fib(1) = 1 (base case)
• fib(n) = fib(n-1) + fib(n-2) for n > 1 (recursive case)

Pseudocode

function fibonacci(n)
    if n == 0 then
        return 0
    elseif n == 1 then
        return 1
    else
        return fibonacci(n - 1) + fibonacci(n - 2)
    endif
endfunction

Python

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(7))    # Output: 13

Trace for fibonacci(4)

fibonacci(4)
= fibonacci(3) + fibonacci(2)
= (fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))
= ((fibonacci(1) + fibonacci(0)) + 1) + (1 + 0)
= ((1 + 0) + 1) + 1
= (1 + 1) + 1
= 2 + 1
= 3

Warning: The recursive Fibonacci implementation is very inefficient — it recalculates the same values many times. For example, fibonacci(5) calls fibonacci(3) twice and fibonacci(2) three times. This results in O(2^n) time complexity.

---

The Call Stack

When a recursive function calls itself, each call is added to the call stack. The call stack stores:

• The function's local variables.
• The return address (where to continue after the function returns).

How the Call Stack Works

factorial(3) called:
  Stack: [factorial(3)]

factorial(3) calls factorial(2):
  Stack: [factorial(3), factorial(2)]

factorial(2) calls factorial(1):
  Stack: [factorial(3), factorial(2), factorial(1)]

factorial(1) calls factorial(0):
  Stack: [factorial(3), factorial(2), factorial(1), factorial(0)]