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