Recursion solves a problem by calling itself on a smaller instance and trusting that call's answer. The problems here — rope cutting, subsets, Tower of Hanoi, Josephus, subset sum and permutations — are the templates for backtracking and dynamic programming later in the course.

How a recursive call runs

Every call pushes a frame (parameters, locals, return address) on the call stack; the frame is popped when the call returns. Work written before the recursive call happens on the way down, work after it happens on the way up — the trace below shows both.

Python

def trace(n):
    if n == 0:                    # base case: answered without another call
        print("base case reached")
        return
    print("enter", n)             # on the way down
    trace(n - 1)                  # smaller instance
    print("exit", n)              # on the way up, after the sub-call finished

trace(3)

C++

#include <iostream>
using namespace std;

void trace(int n) {
    if (n == 0) {                 // base case: answered without another call
        cout << "base case reached\n";
        return;
    }
    cout << "enter " << n << "\n";    // on the way down
    trace(n - 1);                     // smaller instance
    cout << "exit " << n << "\n";     // on the way up, after the sub-call finished
}

int main() { trace(3); }

Java

public class Main {
    static void trace(int n) {
        if (n == 0) {             // base case: answered without another call
            System.out.println("base case reached");
            return;
        }
        System.out.println("enter " + n);   // on the way down
        trace(n - 1);                       // smaller instance
        System.out.println("exit " + n);    // on the way up, after the sub-call finished
    }

    public static void main(String[] args) { trace(3); }
}

JavaScript

function trace(n) {
    if (n === 0) {                // base case: answered without another call
        console.log("base case reached");
        return;
    }
    console.log("enter", n);      // on the way down
    trace(n - 1);                 // smaller instance
    console.log("exit", n);       // on the way up, after the sub-call finished
}

trace(3);

Output

enter 3
enter 2
enter 1
base case reached
exit 1
exit 2
exit 3

Depth 4 = O(n) auxiliary space, even though the function declares no arrays

trace(3)                         call stack (top is the running call)
 └ trace(2)                      ┌──────────┐
    └ trace(1)                   │ trace(0) │ ← base case, 4 frames deep
       └ trace(0)  base case     │ trace(1) │
                                 │ trace(2) │
                                 │ trace(3) │
                                 └──────────┘

Rope cutting problem

Cut a rope of length n into the maximum number of pieces, each of length a, b or c; return -1 if no exact division exists. For n = 23 the best is 12 + 11 (2 pieces); for n = 5 with c = 1 it is five unit pieces.

Three branches per node; a negative length is a dead branch (-1)

maxPieces(5)  a=2 b=5 c=1
├── maxPieces(3)   (cut 2)
│   ├── maxPieces(1)  → ├ (-1) → -1   ├ (-4) → -1   ├ (0) → 0     ⇒ 1
│   ├── maxPieces(-2) → -1
│   └── maxPieces(2)  → … ⇒ 2
│                                          ⇒ 1 + max(1, -1, 2) = 3
├── maxPieces(0)   (cut 5)  → 0            ⇒ 0 + 1 = 1
└── maxPieces(4)   (cut 1)  → … ⇒ 4        ⇒ 5
                                           answer = max(3, 1, 5) = 5

Python

def max_pieces(n, a, b, c):
    if n == 0:
        return 0                      # nothing left to cut: 0 more pieces
    if n < 0:
        return -1                     # this cut overshot the rope: invalid
    res = max(max_pieces(n - a, a, b, c),
              max_pieces(n - b, a, b, c),
              max_pieces(n - c, a, b, c))
    if res == -1:
        return -1                     # none of the three cuts can finish the rope
    return res + 1                    # +1 for the piece cut here

for n, a, b, c in ((5, 2, 5, 1), (23, 12, 9, 11), (5, 4, 2, 6)):
    print(f"n={n} a={a} b={b} c={c} ->", max_pieces(n, a, b, c))

C++

#include <iostream>
#include <algorithm>
using namespace std;

int maxPieces(int n, int a, int b, int c) {
    if (n == 0) return 0;                 // nothing left to cut: 0 more pieces
    if (n < 0) return -1;                 // this cut overshot the rope: invalid
    int res = max({maxPieces(n - a, a, b, c),
                   maxPieces(n - b, a, b, c),
                   maxPieces(n - c, a, b, c)});
    if (res == -1) return -1;             // none of the three cuts can finish the rope
    return res + 1;                       // +1 for the piece cut here
}

int main() {
    int tests[3][4] = {{5, 2, 5, 1}, {23, 12, 9, 11}, {5, 4, 2, 6}};
    for (auto& t : tests)
        cout << "n=" << t[0] << " a=" << t[1] << " b=" << t[2] << " c=" << t[3]
             << " -> " << maxPieces(t[0], t[1], t[2], t[3]) << "\n";
}

Java

public class Main {
    static int maxPieces(int n, int a, int b, int c) {
        if (n == 0) return 0;             // nothing left to cut: 0 more pieces
        if (n < 0) return -1;             // this cut overshot the rope: invalid
        int res = Math.max(maxPieces(n - a, a, b, c),
                  Math.max(maxPieces(n - b, a, b, c), maxPieces(n - c, a, b, c)));
        if (res == -1) return -1;         // none of the three cuts can finish the rope
        return res + 1;                   // +1 for the piece cut here
    }

    public static void main(String[] args) {
        int[][] tests = {{5, 2, 5, 1}, {23, 12, 9, 11}, {5, 4, 2, 6}};
        for (int[] t : tests)
            System.out.println("n=" + t[0] + " a=" + t[1] + " b=" + t[2] + " c=" + t[3]
                               + " -> " + maxPieces(t[0], t[1], t[2], t[3]));
    }
}

JavaScript

function maxPieces(n, a, b, c) {
    if (n === 0) return 0;                // nothing left to cut: 0 more pieces
    if (n < 0) return -1;                 // this cut overshot the rope: invalid
    const res = Math.max(maxPieces(n - a, a, b, c),
                         maxPieces(n - b, a, b, c),
                         maxPieces(n - c, a, b, c));
    if (res === -1) return -1;            // none of the three cuts can finish the rope
    return res + 1;                       // +1 for the piece cut here
}

for (const [n, a, b, c] of [[5, 2, 5, 1], [23, 12, 9, 11], [5, 4, 2, 6]])
    console.log(`n=${n} a=${a} b=${b} c=${c} ->`, maxPieces(n, a, b, c));

Output

n=5 a=2 b=5 c=1 -> 5
n=23 a=12 b=9 c=11 -> 2
n=5 a=4 b=2 c=6 -> -1

Time O(3^n) · Space O(n) recursion depth

Subsets of a string

Generate all 2^n subsets (subsequences keeping the original order) of a string of distinct characters.

Depth n, 2^n leaves — one per subset. Exclude first, so the empty string is printed first

sub("", 0)                                       s = "ABC"
├── exclude A → sub("", 1)
│   ├── exclude B → sub("", 2)
│   │   ├── exclude C → ""      ✔
│   │   └── include C → "C"     ✔
│   └── include B → sub("B", 2)
│       ├── "B"  ✔     └── "BC" ✔
└── include A → sub("A", 1)
    ├── sub("A", 2)  → "A" ✔, "AC" ✔
    └── sub("AB", 2) → "AB" ✔, "ABC" ✔

Python

def subsets(s, curr, i, out):
    if i == len(s):
        out.append(curr if curr else '""')    # a finished subset
        return
    subsets(s, curr, i + 1, out)              # exclude s[i]
    subsets(s, curr + s[i], i + 1, out)       # include s[i]

for s in ("AB", "ABC"):
    out = []
    subsets(s, "", 0, out)
    print(s, "->", " ".join(out), f"({len(out)} subsets)")

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void subsets(const string& s, string curr, int i, vector<string>& out) {
    if (i == (int)s.size()) {
        out.push_back(curr.empty() ? "\"\"" : curr);   // a finished subset
        return;
    }
    subsets(s, curr, i + 1, out);             // exclude s[i]
    subsets(s, curr + s[i], i + 1, out);      // include s[i]
}

int main() {
    for (string s : {"AB", "ABC"}) {
        vector<string> out;
        subsets(s, "", 0, out);
        cout << s << " ->";
        for (const string& x : out) cout << " " << x;
        cout << " (" << out.size() << " subsets)\n";
    }
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void subsets(String s, String curr, int i, List<String> out) {
        if (i == s.length()) {
            out.add(curr.isEmpty() ? "\"\"" : curr);  // a finished subset
            return;
        }
        subsets(s, curr, i + 1, out);                 // exclude s[i]
        subsets(s, curr + s.charAt(i), i + 1, out);   // include s[i]
    }

    public static void main(String[] args) {
        for (String s : new String[]{"AB", "ABC"}) {
            List<String> out = new ArrayList<>();
            subsets(s, "", 0, out);
            System.out.println(s + " -> " + String.join(" ", out) + " (" + out.size() + " subsets)");
        }
    }
}

JavaScript

function subsets(s, curr, i, out) {
    if (i === s.length) {
        out.push(curr === "" ? '""' : curr);  // a finished subset
        return;
    }
    subsets(s, curr, i + 1, out);             // exclude s[i]
    subsets(s, curr + s[i], i + 1, out);      // include s[i]
}

for (const s of ["AB", "ABC"]) {
    const out = [];
    subsets(s, "", 0, out);
    console.log(s, "->", out.join(" "), `(${out.length} subsets)`);
}

Output

AB -> "" B A AB (4 subsets)
ABC -> "" C B BC A AC AB ABC (8 subsets)

Time O(2^n · n) · Space O(n) recursion depth (plus the output)

Tower of Hanoi

Move n discs from peg A (source) to peg C (destination) using peg B (auxiliary), under three rules:

Only one disc moves at a time.
A larger disc may never sit on a smaller one.
Only the top disc of a peg can be moved.

n = 3: the whole tower must end on C in the same order

    A          B          C                 A          B          C
    |          |          |                 |          |          |
   ═╪═         |          |      →          |          |         ═╪═
  ══╪══        |          |                 |          |        ══╪══
 ═══╪═══       |          |                 |          |       ═══╪═══
────┴──────────┴──────────┴──          ────┴──────────┴──────────┴──

TOH(n-1, A, C, B)
Park the top n-1 discs on the auxiliary peg B, using C as the spare.
Move disc n from A to C
The largest disc makes its single move onto the empty destination.
TOH(n-1, B, A, C)
Bring the n-1 discs from B onto C, using A as the spare.

moves(n) = 2 · moves(n−1) + 1 = 2^n − 1 (3 discs → 7, 10 discs → 1023, 64 discs → 1.8 × 10^19)

Python

def toh(n, src, aux, dst):
    if n == 0:
        return 0                              # no discs: no moves
    moves = toh(n - 1, src, dst, aux)         # park n-1 discs on the auxiliary peg
    print(f"Move disc {n} from {src} to {dst}")
    moves += 1 + toh(n - 1, aux, src, dst)    # bring them onto the destination
    return moves

for n in (2, 3):
    print("n =", n)
    print("moves:", toh(n, "A", "B", "C"))

C++

#include <iostream>
using namespace std;

int toh(int n, char src, char aux, char dst) {
    if (n == 0) return 0;                         // no discs: no moves
    int moves = toh(n - 1, src, dst, aux);        // park n-1 discs on the auxiliary peg
    cout << "Move disc " << n << " from " << src << " to " << dst << "\n";
    moves += 1 + toh(n - 1, aux, src, dst);       // bring them onto the destination
    return moves;
}

int main() {
    for (int n : {2, 3}) {
        cout << "n = " << n << "\n";
        int moves = toh(n, 'A', 'B', 'C');      // run first: the moves print inside
        cout << "moves: " << moves << "\n";
    }
}

Java

public class Main {
    static int toh(int n, char src, char aux, char dst) {
        if (n == 0) return 0;                     // no discs: no moves
        int moves = toh(n - 1, src, dst, aux);    // park n-1 discs on the auxiliary peg
        System.out.println("Move disc " + n + " from " + src + " to " + dst);
        moves += 1 + toh(n - 1, aux, src, dst);   // bring them onto the destination
        return moves;
    }

    public static void main(String[] args) {
        for (int n : new int[]{2, 3}) {
            System.out.println("n = " + n);
            System.out.println("moves: " + toh(n, 'A', 'B', 'C'));
        }
    }
}

JavaScript

function toh(n, src, aux, dst) {
    if (n === 0) return 0;                        // no discs: no moves
    let moves = toh(n - 1, src, dst, aux);        // park n-1 discs on the auxiliary peg
    console.log(`Move disc ${n} from ${src} to ${dst}`);
    moves += 1 + toh(n - 1, aux, src, dst);       // bring them onto the destination
    return moves;
}

for (const n of [2, 3]) {
    console.log("n =", n);
    console.log("moves:", toh(n, "A", "B", "C"));
}

Output

n = 2
Move disc 1 from A to B
Move disc 2 from A to C
Move disc 1 from B to C
moves: 3
n = 3
Move disc 1 from A to C
Move disc 2 from A to B
Move disc 1 from C to B
Move disc 3 from A to C
Move disc 1 from B to A
Move disc 2 from B to C
Move disc 1 from A to C
moves: 7

Time O(2^n) moves · Space O(n) recursion depth

Josephus problem (elimination game)

n people stand in a circle numbered 0 … n-1. Starting at 0, every kth person is eliminated and the count restarts from the next person. Which position survives?

Unwinding the recursion from the base case up

jos(1,3) = 0
jos(2,3) = (0 + 3) % 2 = 1
jos(3,3) = (1 + 3) % 3 = 1
jos(4,3) = (1 + 3) % 4 = 0
jos(5,3) = (0 + 3) % 5 = 3
jos(6,3) = (3 + 3) % 6 = 0
jos(7,3) = (0 + 3) % 7 = 3     ← survivor for n = 7, k = 3

Python

def josephus(n, k):
    if n == 1:
        return 0                          # one person left: position 0 survives
    return (josephus(n - 1, k) + k) % n   # shift the smaller game's answer back by k

for n, k in ((7, 3), (8, 2), (5, 2)):
    print(f"n={n} k={k} ->", josephus(n, k))

C++

#include <iostream>
using namespace std;

int josephus(int n, int k) {
    if (n == 1) return 0;                     // one person left: position 0 survives
    return (josephus(n - 1, k) + k) % n;      // shift the smaller game's answer back by k
}

int main() {
    int tests[3][2] = {{7, 3}, {8, 2}, {5, 2}};
    for (auto& t : tests)
        cout << "n=" << t[0] << " k=" << t[1] << " -> " << josephus(t[0], t[1]) << "\n";
}

Java

public class Main {
    static int josephus(int n, int k) {
        if (n == 1) return 0;                 // one person left: position 0 survives
        return (josephus(n - 1, k) + k) % n;  // shift the smaller game's answer back by k
    }

    public static void main(String[] args) {
        int[][] tests = {{7, 3}, {8, 2}, {5, 2}};
        for (int[] t : tests)
            System.out.println("n=" + t[0] + " k=" + t[1] + " -> " + josephus(t[0], t[1]));
    }
}

JavaScript

function josephus(n, k) {
    if (n === 1) return 0;                    // one person left: position 0 survives
    return (josephus(n - 1, k) + k) % n;      // shift the smaller game's answer back by k
}

for (const [n, k] of [[7, 3], [8, 2], [5, 2]])
    console.log(`n=${n} k=${k} ->`, josephus(n, k));

Output

n=7 k=3 -> 3
n=8 k=2 -> 0
n=5 k=2 -> 2

Time O(n) · Space O(n) recursion depth — or O(1) with a loop

To see the eliminations, simulate the circle with a list: the next victim is (idx + k - 1) % size and the count resumes at that index.

Python

def simulate(n, k):
    people = list(range(n))
    idx = 0
    while len(people) > 1:
        idx = (idx + k - 1) % len(people)     # count k people from idx, wrapping around
        removed = people.pop(idx)             # the next person now sits at idx
        print("remove", removed, "-> left:", " ".join(map(str, people)))
    print("survivor:", people[0])

simulate(7, 3)

C++

#include <iostream>
#include <vector>
using namespace std;

void simulate(int n, int k) {
    vector<int> people;
    for (int i = 0; i < n; i++) people.push_back(i);
    int idx = 0;
    while (people.size() > 1) {
        int size = people.size();
        idx = (idx + k - 1) % size;               // count k people from idx, wrapping around
        int removed = people[idx];
        people.erase(people.begin() + idx);       // the next person now sits at idx
        cout << "remove " << removed << " -> left:";
        for (int x : people) cout << " " << x;
        cout << "\n";
    }
    cout << "survivor: " << people[0] << "\n";
}

int main() { simulate(7, 3); }

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void simulate(int n, int k) {
        List<Integer> people = new ArrayList<>();
        for (int i = 0; i < n; i++) people.add(i);
        int idx = 0;
        while (people.size() > 1) {
            idx = (idx + k - 1) % people.size();  // count k people from idx, wrapping around
            int removed = people.remove(idx);     // the next person now sits at idx
            StringBuilder sb = new StringBuilder();
            for (int x : people) sb.append(' ').append(x);
            System.out.println("remove " + removed + " -> left:" + sb);
        }
        System.out.println("survivor: " + people.get(0));
    }

    public static void main(String[] args) { simulate(7, 3); }
}

JavaScript

function simulate(n, k) {
    const people = Array.from({ length: n }, (_, i) => i);
    let idx = 0;
    while (people.length > 1) {
        idx = (idx + k - 1) % people.length;      // count k people from idx, wrapping around
        const [removed] = people.splice(idx, 1);  // the next person now sits at idx
        console.log("remove", removed, "-> left:", people.join(" "));
    }
    console.log("survivor:", people[0]);
}

simulate(7, 3);

Output

remove 2 -> left: 0 1 3 4 5 6
remove 5 -> left: 0 1 3 4 6
remove 1 -> left: 0 3 4 6
remove 6 -> left: 0 3 4
remove 4 -> left: 0 3
remove 0 -> left: 3
survivor: 3

Time O(n²) with list deletion, O(n · k) with a linked circle · Space O(n)

Subset sum (count the subsets)

Count the subsets of arr whose elements add up to sum. For {10, 5, 2, 3, 6} and 8 there are two: {5, 3} and {2, 6}. For sum = 0 the empty subset always counts, so the answer is at least 1.

Each leaf with sum 0 is one valid subset

count(n=3, sum=3)   arr = {1, 2, 3}
├── exclude 3 → count(2, 3)
│   ├── exclude 2 → count(1, 3) → count(0,3)=0, count(0,2)=0          ⇒ 0
│   └── include 2 → count(1, 1) → count(0,1)=0, count(0,0)=1  {1,2}  ⇒ 1
└── include 3 → count(2, 0)
    ├── exclude 2 → count(1, 0) → count(0,0)=1  {3}, count(0,-1)=0   ⇒ 1
    └── include 2 → count(1,-2) → 0                                   ⇒ 0
                                                               total = 2

Python

def count_subsets(arr, n, target):
    if n == 0:
        return 1 if target == 0 else 0            # empty subset: valid only if nothing is left to reach
    return (count_subsets(arr, n - 1, target)                 # exclude arr[n-1]
            + count_subsets(arr, n - 1, target - arr[n - 1]))  # include arr[n-1]

for arr, target in (([10, 5, 2, 3, 6], 8), ([10, 20, 15], 0), ([1, 2, 3], 3)):
    print(" ".join(map(str, arr)), "| sum", target, "->", count_subsets(arr, len(arr), target))

C++

#include <iostream>
#include <vector>
using namespace std;

int countSubsets(const vector<int>& arr, int n, int target) {
    if (n == 0) return target == 0 ? 1 : 0;       // empty subset: valid only if nothing is left to reach
    return countSubsets(arr, n - 1, target)                   // exclude arr[n-1]
         + countSubsets(arr, n - 1, target - arr[n - 1]);     // include arr[n-1]
}

int main() {
    vector<pair<vector<int>, int>> tests = {{{10, 5, 2, 3, 6}, 8}, {{10, 20, 15}, 0}, {{1, 2, 3}, 3}};
    for (auto& [arr, target] : tests) {
        for (int x : arr) cout << x << " ";
        cout << "| sum " << target << " -> " << countSubsets(arr, arr.size(), target) << "\n";
    }
}

Java

public class Main {
    static int countSubsets(int[] arr, int n, int target) {
        if (n == 0) return target == 0 ? 1 : 0;   // empty subset: valid only if nothing is left to reach
        return countSubsets(arr, n - 1, target)               // exclude arr[n-1]
             + countSubsets(arr, n - 1, target - arr[n - 1]); // include arr[n-1]
    }

    public static void main(String[] args) {
        int[][] arrays = {{10, 5, 2, 3, 6}, {10, 20, 15}, {1, 2, 3}};
        int[] targets = {8, 0, 3};
        for (int t = 0; t < arrays.length; t++) {
            StringBuilder sb = new StringBuilder();
            for (int x : arrays[t]) sb.append(x).append(' ');
            System.out.println(sb + "| sum " + targets[t] + " -> "
                               + countSubsets(arrays[t], arrays[t].length, targets[t]));
        }
    }
}

JavaScript

function countSubsets(arr, n, target) {
    if (n === 0) return target === 0 ? 1 : 0;     // empty subset: valid only if nothing is left to reach
    return countSubsets(arr, n - 1, target)                   // exclude arr[n-1]
         + countSubsets(arr, n - 1, target - arr[n - 1]);     // include arr[n-1]
}

for (const [arr, target] of [[[10, 5, 2, 3, 6], 8], [[10, 20, 15], 0], [[1, 2, 3], 3]])
    console.log(arr.join(" "), "| sum", target, "->", countSubsets(arr, arr.length, target));

Output

10 5 2 3 6 | sum 8 -> 2
10 20 15 | sum 0 -> 1
1 2 3 | sum 3 -> 2

Time O(2^n) · Space O(n) recursion depth

Print all permutations of a string

Print every arrangement of the characters of s — there are n! of them for n distinct characters.

n choices at level 0, n−1 at level 1, … → n! leaves. Note the order is not alphabetical

permute(ABC, i=0)
├── swap(0,0) → A|BC  permute(i=1)
│                ├── swap(1,1) → AB|C → ABC ✔
│                └── swap(1,2) → AC|B → ACB ✔   (swap back → ABC)
├── swap(0,1) → B|AC  permute(i=1)
│                ├── BAC ✔
│                └── BCA ✔                       (swap back → ABC)
└── swap(0,2) → C|BA  permute(i=1)
                 ├── CBA ✔
                 └── CAB ✔                       (swap back → ABC)

Python

def permute(chars, i, out):
    n = len(chars)
    if i == n - 1:
        out.append("".join(chars))            # every position fixed: one permutation
        return
    for j in range(i, n):
        chars[i], chars[j] = chars[j], chars[i]   # choose chars[j] for position i
        permute(chars, i + 1, out)
        chars[i], chars[j] = chars[j], chars[i]   # backtrack: undo the swap

for s in ("AB", "ABC"):
    out = []
    permute(list(s), 0, out)
    print(s, "->", " ".join(out))

C++

#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;

void permute(string& s, int i, vector<string>& out) {
    int n = s.size();
    if (i == n - 1) {
        out.push_back(s);                     // every position fixed: one permutation
        return;
    }
    for (int j = i; j < n; j++) {
        swap(s[i], s[j]);                     // choose s[j] for position i
        permute(s, i + 1, out);
        swap(s[i], s[j]);                     // backtrack: undo the swap
    }
}

int main() {
    for (string s : {"AB", "ABC"}) {
        vector<string> out;
        string work = s;
        permute(work, 0, out);
        cout << s << " ->";
        for (const string& p : out) cout << " " << p;
        cout << "\n";
    }
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void permute(char[] s, int i, List<String> out) {
        int n = s.length;
        if (i == n - 1) {
            out.add(new String(s));           // every position fixed: one permutation
            return;
        }
        for (int j = i; j < n; j++) {
            char t = s[i]; s[i] = s[j]; s[j] = t;   // choose s[j] for position i
            permute(s, i + 1, out);
            t = s[i]; s[i] = s[j]; s[j] = t;        // backtrack: undo the swap
        }
    }

    public static void main(String[] args) {
        for (String s : new String[]{"AB", "ABC"}) {
            List<String> out = new ArrayList<>();
            permute(s.toCharArray(), 0, out);
            System.out.println(s + " -> " + String.join(" ", out));
        }
    }
}

JavaScript

function permute(chars, i, out) {
    const n = chars.length;
    if (i === n - 1) {
        out.push(chars.join(""));             // every position fixed: one permutation
        return;
    }
    for (let j = i; j < n; j++) {
        [chars[i], chars[j]] = [chars[j], chars[i]];   // choose chars[j] for position i
        permute(chars, i + 1, out);
        [chars[i], chars[j]] = [chars[j], chars[i]];   // backtrack: undo the swap
    }
}

for (const s of ["AB", "ABC"]) {
    const out = [];
    permute([...s], 0, out);
    console.log(s, "->", out.join(" "));
}

Output

AB -> AB BA
ABC -> ABC ACB BAC BCA CBA CAB

Time O(n! · n) · Space O(n) recursion depth, swapping in place

Recursion trees at a glance

The cost of a recursive solution is read off its tree: time is roughly the number of nodes (branching factor to the power of the depth), auxiliary space is the height. Overlapping subproblems (the same node appearing many times) are the signal to memoise.

Problem	Branching	Depth	Time	Aux space	Overlap?
Rope cutting	3	`n / min(a,b,c)`	`O(3^n)`	`O(n)`	yes → DP `O(n)`
Subsets of a string	2	`n`	`O(2^n · n)`	`O(n)`	no — every leaf is a distinct answer
Tower of Hanoi	2	`n`	`O(2^n)`	`O(n)`	no — every move is output
Josephus	1	`n`	`O(n)`	`O(n)` (loop: `O(1)`)	—
Subset sum count	2	`n`	`O(2^n)`	`O(n)`	yes → DP `O(n · sum)`
Permutations	`n, n-1, …, 1`	`n`	`O(n! · n)`	`O(n)`	no — every leaf is a distinct answer

Interview Q&A

What are the two things every recursive function needs?

What is tail recursion, and does it help?

Why is Tower of Hanoi O(2^n) and not O(n)? There is only one print per call.

How do you turn an exponential recursion into a fast one?

Recursion vs iteration — when to pick which?

What does the Josephus formula (jos(n-1, k) + k) % n actually mean?