Overview#

Recursion is a programming method in which a function calls itself directly or indirectly. It breaks a large problem into smaller problems of the same structure, stops splitting through a termination condition, and combines the results during the return process.

Prerequisites

• Call stack: each recursive call saves the current execution context
• Divide and conquer: recursion is often used to break a problem into subproblems of the same structure
• Tree structure: trees are naturally recursive by definition, and traversal is best expressed recursively

Problem Definition#

When a problem can be described as “the current answer depends on a smaller instance of the same kind of problem,” recursion can be considered.

Core Principle: Step-by-Step Illustration#

Take factorial factorial(4) as an example:

Recursion involves two directions:

1. Descending: continuously break the problem into smaller pieces until the termination condition is hit.
2. Returning: after subproblems return their results, merge them layer by layer into the final answer.

If the termination condition is unreachable, recursion will call indefinitely and eventually cause a stack overflow.

Detailed Algorithm Steps#

1
Algorithm: RecursiveSolve(problem)
2
Input: current problem problem
3
Output: answer to problem
4

5
1. If problem is the smallest problem, return the known answer
6
2. Transform problem into one or more smaller problems of the same kind
7
3. Recursively solve the subproblems
8
4. Combine the subproblem results into the answer to the current problem
9
5. Return the answer

Complexity analysis:

TypeScript Implementation#

1
function factorial(n: number): number {
2
  if (n <= 1) return 1;
3
  return n * factorial(n - 1);
4
}

1
function fib(n: number): number {
2
  if (n <= 1) return n;
3
  return fib(n - 1) + fib(n - 2);
4
}
5

6
function fibMemo(n: number, memo = new Map<number, number>()): number {
7
  if (n <= 1) return n;
8
  if (memo.has(n)) return memo.get(n)!;
9

10
  const value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
11
  memo.set(n, value);
12
  return value;
13
}

1
function hanoi(n: number, from: string, to: string, via: string): void {
2
  if (n === 1) {
3
    console.log(`${from} -> ${to}`);
4
    return;
5
  }
6

7
  hanoi(n - 1, from, via, to);
8
  console.log(`${from} -> ${to}`);
9
  hanoi(n - 1, via, to, from);
10
}

1
function myPow(x: number, n: number): number {
2
  if (n === 0) return 1;
3
  if (n < 0) return 1 / myPow(x, -n);
4

5
  const half = myPow(x, Math.floor(n / 2));
6
  return n % 2 === 0 ? half * half : half * half * x;
7
}

1
interface TreeNode {
2
  val: number;
3
  left: TreeNode | null;
4
  right: TreeNode | null;
5
}
6

7
function maxDepth(root: TreeNode | null): number {
8
  if (root === null) return 0;
9
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
10
}

1
function sumRecursive(n: number): number {
2
  if (n === 0) return 0;
3
  return n + sumRecursive(n - 1);
4
}
5

6
function sumIterative(n: number): number {
7
  let sum = 0;
8
  for (let i = 1; i <= n; i++) {
9
    sum += i;
10
  }
11
  return sum;
12
}

Engineering Optimization: Memoization and Stack Depth Control#

Tail-recursive code is closer to iteration, but in JavaScript/TypeScript environments you cannot rely on the runtime to automatically optimize the call stack.

Applications and Limitations#

Summary#

Key points:

1. The three essential elements of recursion are the termination condition, the recurrence relation, and the return value.
2. Recursion is suitable for problems that are naturally hierarchical, such as tree-shaped, divide-and-conquer, and backtracking problems.
3. Overlapping subproblems require memoization to avoid exponential repeated computation.
4. When depth is uncontrollable, prefer rewriting to an explicit stack or iteration.