Show understanding of recursion

19.2 Recursion

What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. Think of it like a set of Russian nesting dolls: each doll contains a smaller one, and you keep opening them until you reach the tiniest doll. In code, the function keeps calling itself with a simpler version of the problem until it reaches a base case that can be solved directly. 📦🔁

Key Components

• Base Case: The simplest instance of the problem that can be answered without further recursion.
• Recursive Case: The part where the function calls itself with a smaller or simpler input.
• Progression: Each recursive call must move closer to the base case to avoid infinite loops.

Example: Factorial

The factorial of a positive integer $n$ (written $n!$) is the product of all positive integers up to $n$. $$ n! = n \times (n-1) \times \dots \times 1 $$ In recursive form:

int factorial(int n) {
    if (n == 0) return 1;          // Base case
    else return n * factorial(n-1); // Recursive case
}

Call Stack Visualisation

When you call factorial(3), the stack grows like this:

Common Pitfalls

• Missing a base case → infinite recursion and stack overflow.
• Not reducing the problem size → same issue as above.
• Using recursion for very deep calls can be memory‑intensive; consider iterative solutions or tail recursion.

Exam Tips 📚