🔄 PHP Recursion Basics

Parent: Recursion & Backtracking Index

---

What is Recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive solution has two parts:

1. Base Case — The condition that stops the recursion (prevents infinite loop)
2. Recursive Case — The function calls itself with a smaller/simpler input

function countdown(int $n): void
{
    // Base case — stop here
    if ($n <= 0) {
        echo "Done!\n";
        return;
    }

    echo "$n\n";

    // Recursive case — smaller input (n-1)
    countdown($n - 1);
}

countdown(5);
// Output: 5, 4, 3, 2, 1, Done!

---

How the Call Stack Works

Every function call gets its own stack frame (its own memory for variables). When recursion runs, frames pile up like plates:

countdown(3) called
  └─ countdown(2) called
       └─ countdown(1) called
            └─ countdown(0) called → prints "Done!" → returns
            countdown(1) returns
       countdown(2) returns
  countdown(3) returns

Stack Overflow happens when recursion is too deep (PHP default limit ~few thousand). Always ensure your base case is reachable.

---

Q1. Factorial

Problem: Compute n! = n × (n-1) × (n-2) × ... × 1

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

n! = n × (n-1)! — the problem reduces to a smaller version of itself.

Step 2 — Brute force: Iterative loop is fine, but recursion demonstrates the concept cleanly.

Step 3 — Recursive insight:

- Base case: 0! = 1 and 1! = 1

- Recursive case: factorial(n) = n × factorial(n-1)

Step 4 — Algorithm:

1. If n <= 1, return 1

2. Return n × factorial(n-1)

Step 5 — Edge cases:

- n=0: return 1 (0! is defined as 1)

- Negative input: undefined, return 0 or throw

function factorial(int $n): int
{
    // Base case
    if ($n <= 1) return 1;

    // Recursive case
    return $n * factorial($n - 1);
}

// Call stack for factorial(4):
// factorial(4) = 4 * factorial(3)
//                    = 3 * factorial(2)
//                         = 2 * factorial(1)
//                              = 1  ← base case
//                         = 2 * 1 = 2
//                    = 3 * 2 = 6
//              = 4 * 6 = 24

echo factorial(5);  // 120
echo factorial(0);  // 1
echo factorial(10); // 3628800

Time: O(n) | Space: O(n) — n frames on call stack

---

Q2. Fibonacci Number

Problem: Return the nth Fibonacci number. F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Each answer depends on two smaller sub-problems → tree recursion.

Step 2 — Brute force (naive):

Directly apply the formula recursively → O(2ⁿ) because many sub-problems are recalculated.

Step 3 — Optimal insight — Memoization:

Cache already-computed results. fib(30) is only computed once, not 2^30 times.

Step 4 — Algorithm:

1. If n <= 1, return n

2. If memo[n] exists, return it

3. memo[n] = fib(n-1) + fib(n-2); return memo[n]

Step 5 — Edge cases:

- n=0 → 0, n=1 → 1

// ── Naive — O(2ⁿ) — DO NOT USE for large n ──
function fibNaive(int $n): int
{
    if ($n <= 1) return $n;
    return fibNaive($n - 1) + fibNaive($n - 2);
}

// ── Memoized — O(n) time, O(n) space ──
function fib(int $n, array &$memo = []): int
{
    if ($n <= 1) return $n;
    if (isset($memo[$n])) return $memo[$n];

    $memo[$n] = fib($n - 1, $memo) + fib($n - 2, $memo);
    return $memo[$n];
}

// ── Bottom-up DP — O(n) time, O(1) space (best) ──
function fibDP(int $n): int
{
    if ($n <= 1) return $n;
    $a = 0; $b = 1;
    for ($i = 2; $i <= $n; $i++) {
        [$a, $b] = [$b, $a + $b];
    }
    return $b;
}

echo fib(10);   // 55
echo fib(40);   // 102334155
echo fibDP(50); // 12586269025

Time: O(n) memoized | Space: O(n)

---

Q3. Sum of 1 to N

Problem: Compute the sum 1 + 2 + 3 + ... + n using recursion.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

sum(n) = n + sum(n-1) — classic linear recursion.

Step 2 — Base case: sum(0) = 0 or sum(1) = 1

Step 3 — Algorithm:

1. If n == 0, return 0

2. Return n + sumN(n-1)

function sumN(int $n): int
{
    if ($n <= 0) return 0;        // Base case
    return $n + sumN($n - 1);    // Recursive case
}

// Iterative comparison
function sumNIterative(int $n): int
{
    return ($n * ($n + 1)) / 2;  // Math formula O(1)
}

echo sumN(10);           // 55
echo sumNIterative(100); // 5050

Time: O(n) | Space: O(n)

---

Q4. Power (x to the n)

Problem: Compute x^n (x raised to power n). Handle negative exponents too.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

x^n = x × x^(n-1) — but we can do better with fast exponentiation.

Step 2 — Brute force:

Multiply x by itself n times → O(n). Too slow for large n.

Step 3 — Fast Power (Divide & Conquer):

x^n = x^(n/2) × x^(n/2) (if n is even) — halves the problem each step → O(log n).

Step 4 — Algorithm:

1. If n == 0, return 1

2. If n is negative, return 1 / power(x, -n)

3. half = power(x, n/2)

4. If n is even: return half × half

5. If n is odd: return x × half × half

Step 5 — Edge cases:

- x=0, n=0 → defined as 1

- Negative exponent → 1 / x^|n|

function myPow(float $x, int $n): float
{
    // Base case
    if ($n === 0) return 1.0;

    // Negative exponent
    if ($n < 0) return 1.0 / myPow($x, -$n);

    // Fast power: divide & conquer
    $half = myPow($x, intdiv($n, 2));

    if ($n % 2 === 0) {
        return $half * $half;              // Even: x^n = (x^n/2)²
    } else {
        return $x * $half * $half;        // Odd: x^n = x * (x^(n-1)/2)²
    }
}

echo myPow(2.0, 10);   // 1024.0
echo myPow(2.0, -2);   // 0.25
echo myPow(3.0, 5);    // 243.0

Time: O(log n) | Space: O(log n)

---

Q5. Reverse a String Using Recursion

Problem: Reverse a string using recursion (no built-in reverse).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Reverse("hello") = Reverse("ello") + "h" — take last char, recurse on rest.

Step 2 — Algorithm:

1. If string length <= 1, return it (base case)

2. Return reverseStr(substring from index 1) + first character

function reverseStr(string $s): string
{
    // Base case: empty string or single char
    if (strlen($s) <= 1) return $s;

    // Recursive case: reverse rest + first char
    return reverseStr(substr($s, 1)) . $s[0];
}

echo reverseStr("hello");    // "olleh"
echo reverseStr("recursion"); // "noisrucer"
echo reverseStr("a");         // "a"

Time: O(n²) due to string concatenation | Space: O(n)

---

Q6. Check if String is Palindrome (Recursive)

Problem: Check if a string is a palindrome using recursion.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Palindrome("racecar"): first == last? → recurse on middle. Two-pointer problem expressed recursively.

Step 2 — Algorithm:

1. Base case: if length <= 1, return true

2. If first char != last char, return false

3. Recurse on s[1..n-2]

Step 3 — Edge cases:

- Empty string: palindrome (true)

- Single char: palindrome (true)

function isPalindromeRec(string $s, int $left = 0, ?int $right = null): bool
{
    if ($right === null) $right = strlen($s) - 1;

    // Base case: pointers meet or cross
    if ($left >= $right) return true;

    // Mismatch — not a palindrome
    if ($s[$left] !== $s[$right]) return false;

    // Recurse on inner substring
    return isPalindromeRec($s, $left + 1, $right - 1);
}

var_dump(isPalindromeRec("racecar")); // true
var_dump(isPalindromeRec("hello"));   // false
var_dump(isPalindromeRec("abba"));    // true
var_dump(isPalindromeRec("a"));       // true

Time: O(n) | Space: O(n)

---

Q7. Sum of Digits

Problem: Find the sum of digits of a number recursively.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

sumDigits(1234) = 4 + sumDigits(123) — peel last digit each call.

Step 2 — Algorithm:

1. Base case: n < 10, return n

2. Return (n % 10) + sumDigits(n / 10)

function sumDigits(int $n): int
{
    $n = abs($n); // handle negatives
    if ($n < 10) return $n;  // Base case: single digit
    return ($n % 10) + sumDigits(intdiv($n, 10));
}

echo sumDigits(1234);  // 10  (1+2+3+4)
echo sumDigits(9999);  // 36
echo sumDigits(0);     // 0

Time: O(digits) = O(log n) | Space: O(log n)

---

Recursion vs Iteration — Side-by-side

// Sum 1..n

// ITERATIVE — O(n) time, O(1) space
function sumIterative(int $n): int {
    $sum = 0;
    for ($i = 1; $i <= $n; $i++) $sum += $i;
    return $sum;
}

// RECURSIVE — O(n) time, O(n) space (call stack)
function sumRecursive(int $n): int {
    if ($n <= 0) return 0;
    return $n + sumRecursive($n - 1);
}

// FORMULA — O(1) time, O(1) space (best!)
function sumFormula(int $n): int {
    return ($n * ($n + 1)) / 2;
}

Rule of thumb: If a problem can be solved equally well iteratively, prefer iteration (no stack overhead). Use recursion when the problem structure is inherently recursive (trees, backtracking, divide & conquer).

---

Common Mistakes