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