Recursion

This lesson covers recursion — a powerful programming technique in which a function calls itself to solve a problem. Recursion is a key topic in A-Level Computer Science and is closely linked to mathematical induction, tree traversal, and divide-and-conquer algorithms.

---

What is Recursion?

Recursion is a technique where a subroutine (function or procedure) calls itself as part of its execution. Every recursive solution must have:

1. A base case — a condition under which the function stops calling itself and returns a value directly.
2. A recursive case — the part where the function calls itself with a modified argument, moving toward the base case.

Without a base case, recursion would continue indefinitely, causing a stack overflow error.

Simple Example: Factorial

The factorial of a non-negative integer n (written n!) is defined as:

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

Pseudocode

FUNCTION factorial(n: INTEGER) RETURNS INTEGER
    IF n = 0 THEN
        RETURN 1                    // Base case
    ELSE
        RETURN n * factorial(n - 1) // Recursive case
    END IF
END FUNCTION

Python

def factorial(n: int) -> int:
    if n == 0:
        return 1                    # Base case
    else:
        return n * factorial(n - 1) # Recursive case

print(factorial(5))  # Output: 120

---

Tracing Recursive Calls

Understanding recursion requires tracing through the call stack. Here is the trace for factorial(4):

Call	n	Action	Returns
factorial(4)	4	4 * factorial(3)	24
factorial(3)	3	3 * factorial(2)	6
factorial(2)	2	2 * factorial(1)	2
factorial(1)	1	1 * factorial(0)	1
factorial(0)	0	Base case reached	1

The calls unwind from the bottom up: factorial(0) returns 1, then factorial(1) returns 1*1=1, and so on, until factorial(4) returns 24.

Exam Tip: You are very likely to be asked to trace through a recursive function and show the call stack or return values. Practise this with factorial, Fibonacci, and power functions.

---

The Call Stack

When a function calls itself, each call is placed on the call stack — a data structure that stores information about active function calls. Each stack frame contains:

• The function's local variables
• The parameter values
• The return address (where to resume execution after the call returns)

Call stack for factorial(4):

| factorial(0) |  <- top (most recent)
| factorial(1) |
| factorial(2) |
| factorial(3) |
| factorial(4) |  <- bottom (first call)

When the base case is reached, stack frames are popped (removed) one by one as each call returns.

Stack Overflow

If the base case is never reached (or the recursion depth is too large), the call stack runs out of space, causing a stack overflow error. Python has a default recursion limit of about 1000 calls.

---

Classic Recursive Examples

Fibonacci Sequence

The Fibonacci sequence is defined as:

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