🔄 PHP Recursion Patterns

Parent: Recursion & Backtracking Index

---

Overview

Once you understand basic recursion, these are the key patterns that appear repeatedly in interviews and real problems.

---

Pattern 1 — Tower of Hanoi

Problem: Move n disks from rod A to rod C using B as helper. Larger disk can never go on smaller.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

To move n disks: move top n-1 to B, move disk n to C, move n-1 from B to C. Classic 3-step recursion.

Step 2 — Why recursion fits:

Problem reduces perfectly: n disks → n-1 disks (same sub-problem, different rods).

Step 3 — Algorithm:

1. Base case: n=1 → move disk from source to dest

2. Move top n-1 disks: source → helper

3. Move disk n: source → destination

4. Move n-1 disks: helper → destination

Step 4 — Edge cases:

- n=1: single move

- Total moves = 2ⁿ - 1

function hanoi(int $n, string $from, string $to, string $via): void
{
    // Base case: one disk — just move it
    if ($n === 1) {
        echo "Move disk 1 from $from to $to\n";
        return;
    }

    // Step 1: Move top n-1 disks from source to helper
    hanoi($n - 1, $from, $via, $to);

    // Step 2: Move largest disk from source to destination
    echo "Move disk $n from $from to $to\n";

    // Step 3: Move n-1 disks from helper to destination
    hanoi($n - 1, $via, $to, $from);
}

hanoi(3, 'A', 'C', 'B');
// Move disk 1 from A to C
// Move disk 2 from A to B
// Move disk 1 from C to B
// Move disk 3 from A to C
// Move disk 1 from B to A
// Move disk 2 from B to C
// Move disk 1 from A to C

Time: O(2ⁿ) — 2ⁿ-1 total moves | Space: O(n)

---

Pattern 2 — Generate All Subsets

Problem: Return all possible subsets (power set) of an array. Example: [1,2,3] → [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Each element has 2 choices: include or exclude. This creates a binary decision tree → 2ⁿ subsets.

Step 2 — Decision tree for [1,2,3]:

```

Start []

├── include 1: [1]

│ ├── include 2: [1,2]

│ │ ├── include 3: [1,2,3] ✓

│ │ └── exclude 3: [1,2] ✓

│ └── exclude 2: [1]

│ ├── include 3: [1,3] ✓

│ └── exclude 3: [1] ✓

└── exclude 1: []

... (similar)

```

Step 3 — Algorithm:

1. At each index, choose to include or exclude current element

2. Base case: index == len(array) → add current subset to result

Step 4 — Edge cases:

- Empty array: result = [[]]

function subsets(array $nums): array
{
    $result  = [];
    $current = [];

    function generate(array $nums, int $idx, array &$current, array &$result): void
    {
        // Base case: processed all elements
        if ($idx === count($nums)) {
            $result[] = $current;
            return;
        }

        // Choice 1: INCLUDE nums[idx]
        $current[] = $nums[$idx];
        generate($nums, $idx + 1, $current, $result);

        // Choice 2: EXCLUDE nums[idx] (backtrack)
        array_pop($current);
        generate($nums, $idx + 1, $current, $result);
    }

    generate($nums, 0, $current, $result);
    return $result;
}

$sets = subsets([1, 2, 3]);
// [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
echo count($sets); // 8 = 2³

Time: O(2ⁿ) | Space: O(n) call stack depth

---

Pattern 3 — Generate All Permutations

Problem: Return all permutations of an array. Example: [1,2,3] → 6 permutations.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Permutation = ordering. At each position, try each unused element. Track used elements with a swap or a visited array.

Step 2 — Swap approach (in-place):

Fix one element at position i, recursively permute the rest. Then swap back (backtrack).

Step 3 — Algorithm:

1. Base case: index == length → add copy of array to result

2. For j from index to end: swap(index, j), recurse(index+1), swap back

Step 4 — Edge cases:

- n=1: one permutation (the array itself)

- Duplicates: need a visited set to avoid duplicate results

function permutations(array $nums): array
{
    $result = [];

    function permute(array &$nums, int $start, array &$result): void
    {
        // Base case: all positions filled
        if ($start === count($nums)) {
            $result[] = $nums;  // copy of current arrangement
            return;
        }

        for ($j = $start; $j < count($nums); $j++) {
            // Choose: fix nums[j] at position $start
            [$nums[$start], $nums[$j]] = [$nums[$j], $nums[$start]];

            // Explore: permute the rest
            permute($nums, $start + 1, $result);

            // Un-choose (backtrack): restore original order
            [$nums[$start], $nums[$j]] = [$nums[$j], $nums[$start]];
        }
    }

    permute($nums, 0, $result);
    return $result;
}

$perms = permutations([1, 2, 3]);
foreach ($perms as $p) echo implode(',', $p) . "\n";
// 1,2,3 / 1,3,2 / 2,1,3 / 2,3,1 / 3,2,1 / 3,1,2
echo count($perms); // 6 = 3!

Time: O(n × n!) — n! permutations, each costs O(n) to copy | Space: O(n)

---

Pattern 4 — Combination Sum

Problem: Find all combinations of numbers from $candidates that sum to $target. Each number can be reused.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Unlimited pick from array to reach target = backtracking with reuse.

Step 2 — Key trick:

At each step, either pick the current candidate again (don't advance index) or move to the next candidate. This avoids duplicates.

Step 3 — Algorithm:

1. Base case: target == 0 → found a valid combination

2. Base case: target < 0 or index out of bounds → prune (return)

3. Include candidates[index]: recurse with same index, reduced target

4. Skip candidates[index]: recurse with index+1, same target

function combinationSum(array $candidates, int $target): array
{
    sort($candidates); // sort to prune early
    $result  = [];
    $current = [];

    function backtrack(
        array $candidates,
        int   $target,
        int   $start,
        array &$current,
        array &$result
    ): void {
        // Found valid combination
        if ($target === 0) {
            $result[] = $current;
            return;
        }

        for ($i = $start; $i < count($candidates); $i++) {
            // Prune: candidates are sorted, if too large → stop
            if ($candidates[$i] > $target) break;

            // Choose
            $current[] = $candidates[$i];

            // Explore (same index — reuse allowed)
            backtrack($candidates, $target - $candidates[$i], $i, $current, $result);

            // Un-choose
            array_pop($current);
        }
    }

    backtrack($candidates, $target, 0, $current, $result);
    return $result;
}

$result = combinationSum([2, 3, 6, 7], 7);
// [[2,2,3], [7]]

$result = combinationSum([2, 3, 5], 8);
// [[2,2,2,2], [2,3,3], [3,5]]

Time: O(n^(T/M)) where T=target, M=min candidate | Space: O(T/M)

---

Pattern 5 — Binary Search (Recursive)

Problem: Implement binary search recursively.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Divide and conquer — cut search space in half each call.

Step 2 — Algorithm:

1. Base case: left > right → return -1 (not found)

2. mid = (left + right) / 2

3. If target == arr[mid] → return mid

4. If target < arr[mid] → search left half

5. Else → search right half

function binarySearch(array $arr, int $target, int $left = 0, ?int $right = null): int
{
    if ($right === null) $right = count($arr) - 1;

    // Base case: search space empty
    if ($left > $right) return -1;

    $mid = intdiv($left + $right, 2);

    if ($arr[$mid] === $target) return $mid;
    if ($target < $arr[$mid])   return binarySearch($arr, $target, $left, $mid - 1);
    return binarySearch($arr, $target, $mid + 1, $right);
}

$arr = [1, 3, 5, 7, 9, 11, 13];
echo binarySearch($arr, 7);   // 3 (index)
echo binarySearch($arr, 6);   // -1 (not found)

Time: O(log n) | Space: O(log n) — recursive calls

---

Pattern 6 — Merge Sort (Recursive)

Problem: Sort an array using merge sort (divide and conquer).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Split array in half → sort each half → merge. Classic divide and conquer.

Step 2 — Algorithm:

1. Base case: array length <= 1 → already sorted

2. Split into left and right halves

3. Recursively sort each half

4. Merge the two sorted halves

function mergeSort(array $arr): array
{
    $n = count($arr);
    if ($n <= 1) return $arr; // Base case

    // Divide
    $mid   = intdiv($n, 2);
    $left  = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));

    // Conquer (merge)
    return merge($left, $right);
}

function merge(array $left, array $right): array
{
    $result = [];
    $i = $j = 0;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) $result[] = $left[$i++];
        else                          $result[] = $right[$j++];
    }

    // Append remaining
    while ($i < count($left))  $result[] = $left[$i++];
    while ($j < count($right)) $result[] = $right[$j++];

    return $result;
}

$sorted = mergeSort([38, 27, 43, 3, 9, 82, 10]);
echo implode(', ', $sorted); // 3, 9, 10, 27, 38, 43, 82

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

---

Pattern Summary