🔄 Recursion - Functions Calling Themselves

🟡 Intermediate Core Concept 60 min read

🎯 What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem by breaking it into smaller, identical subproblems. Every recursive solution has two essential parts: a base case (stopping condition) and a recursive case (self-call with smaller input).

🪆 Real-Life Analogy: Russian Dolls

Opening a Russian nesting doll: You open one doll to find a smaller version inside. You keep opening until you reach the smallest doll that cannot be opened. The smallest doll is your base case. The process of opening each doll is the recursive case.

🧬 Anatomy of Recursion

1️⃣ Base Case (Stopping Condition)

The simplest version of the problem that can be solved directly without further recursion. Without this, you get infinite recursion → stack overflow!

2️⃣ Recursive Case (Self-Call)

The function calls itself with a modified/smaller input that moves toward the base case. Each call adds a frame to the call stack.

💡 Classic Recursion Examples

1. Factorial (The Hello World of Recursion)

function factorial(int $n): int {
    // Base case: 0! = 1, 1! = 1
    if ($n <= 1) return 1;
    // Recursive case: n! = n * (n-1)!
    return $n * factorial($n - 1);
}
echo factorial(5); // 120 (5 * 4 * 3 * 2 * 1)

📝 Dry Run: factorial(5)
factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 ← Base Case!
Then unwinds: 1→2→6→24→120

2. Fibonacci Sequence

function fibonacci(int $n): int {
    if ($n <= 1) return $n;          // Base case
    return fibonacci($n - 1) + fibonacci($n - 2); // Recursive
}
// fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5

// ⚠️ This has O(2ⁿ) time! Use memoization for efficiency.

3. Sum of Array (Recursive)

function recursiveSum(array $arr, int $n): int {
    if ($n <= 0) return 0;                    // Base: empty array
    return $arr[$n - 1] + recursiveSum($arr, $n - 1);
}
echo recursiveSum([1, 2, 3, 4, 5], 5); // 15

4. Binary Search (Recursive)

function binarySearchRec(array $arr, int $target, int $low, int $high): int {
    if ($low > $high) return -1; // Base: not found

    $mid = intdiv($low + $high, 2);
    if ($arr[$mid] === $target) return $mid;   // Base: found
    if ($arr[$mid] > $target)
        return binarySearchRec($arr, $target, $low, $mid - 1);
    else
        return binarySearchRec($arr, $target, $mid + 1, $high);
}

5. Tower of Hanoi (Classic)

function towerOfHanoi(int $n, string $from, string $to, string $aux): void {
    if ($n === 1) {
        echo "Move disk 1 from $from to $to\n";
        return;
    }
    towerOfHanoi($n - 1, $from, $aux, $to);
    echo "Move disk $n from $from to $to\n";
    towerOfHanoi($n - 1, $aux, $to, $from);
}
towerOfHanoi(3, 'A', 'C', 'B');
// Moves: A→C, A→B, C→B, A→C, B→A, B→C, A→C (7 moves = 2³-1)

📂 Types of Recursion

Direct	Function calls itself directly	factorial(n) → factorial(n-1)
Indirect	Function A calls B, B calls A	isEven() ↔ isOdd()
Tail	Recursive call is the last operation	Tail-recursive factorial
Non-Tail	Operations happen after recursive call	Standard factorial (multiply after)
Tree	Multiple recursive calls per invocation	Fibonacci (2 calls), Merge Sort

🔄 Iterative vs Recursive

✅ Recursion Pros

Cleaner, more readable code for tree/graph problems
Natural fit for divide-and-conquer
Easier to prove correctness

⚠️ Recursion Cons

Higher memory (call stack overhead)
Risk of stack overflow for deep recursion
Often slower due to function call overhead
Can cause repeated work (e.g., naive Fibonacci)

⚠️ Stack Overflow & Recursion Limit

// PHP has a recursion limit (default ~100-256 nested calls)
// Always ensure your base case is reachable!

// Bad: infinite recursion
function bad(int $n): void { bad($n + 1); } // Stack overflow!

// Good: tail recursion (PHP doesn't optimize this, but some languages do)
function sumTail(int $n, int $acc = 0): int {
    if ($n <= 0) return $acc;
    return sumTail($n - 1, $acc + $n);
}

💼 Interview Questions

Base Case (stopping condition) and Recursive Case (self-call moving toward base case). Missing either = broken recursion.

Choose recursion for tree/graph traversals, backtracking (N-Queens, Sudoku), divide-and-conquer (Merge Sort), and when the problem has a natural recursive structure. Use iteration when performance and memory are critical.

Use an explicit stack data structure to simulate the call stack. Push initial state, loop while stack isn't empty, pop and process, push subproblems. This is how compilers implement recursion internally.

📝 Quick Quiz

📋 Recursion Cheat Sheet

Base Case	Simplest input, stops recursion
Recursive Case	Breaks problem into smaller subproblem
Call Stack	LIFO structure holding function frames
Tail Recursion	Recursive call is last; can be optimized to iteration
Memoization	Cache results to avoid repeated computation

Previous: Strings Next: Linked List