Advanced Recursion (Tree Recursion, Tail Call Optimization)

0/12 in this phase0/57 across the roadmap

📖 Concept

Advanced recursion patterns go beyond simple linear recursion. Understanding these unlocks trees, graphs, and complex problem decomposition.

Types of recursion:

Linear recursion — One recursive call: factorial(n) = n * factorial(n-1)
Tree recursion — Multiple recursive calls: fibonacci(n) = fib(n-1) + fib(n-2)
Tail recursion — Recursive call is the LAST operation (can be optimized to O(1) space)
Mutual recursion — Function A calls B, B calls A (e.g., even/odd checker)
Nested recursion — Argument is a recursive call: f(f(n-1))

Tree recursion patterns:

Each call spawns multiple sub-calls → creates a tree of calls
Classic: fibonacci, power set, tree traversal
Time is usually exponential without memoization

Tail Call Optimization (TCO):

When the recursive call is in tail position (nothing happens after it returns)
The compiler can reuse the current stack frame → O(1) space
JavaScript: TCO only in Safari strict mode; Node/Chrome do NOT support it
Practical advice: Convert to iteration for deep recursion

Converting to tail recursion:

// NOT tail recursive — work after the recursive call
function factorial(n) { return n * factorial(n-1); }

// TAIL recursive — accumulator carries the result
function factorial(n, acc = 1) { return n <= 1 ? acc : factorial(n-1, n*acc); }

🏠 Real-world analogy: Tree recursion is like a phone tree where each person calls two more people. Linear recursion is one person calling the next in a chain. Tail recursion is like passing a baton in a relay — the previous runner can leave immediately.

💻 Code Example

codeTap to expand ⛶

1// TREE RECURSION — Binary tree traversal
2interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }
3
4function maxDepth(root: TreeNode | null): number {
5  if (!root) return 0;
6  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
7}
8
9// TREE RECURSION — Generate all subsets
10function subsets(nums: number[]): number[][] {
11  if (nums.length === 0) return [[]];
12  const first = nums[0];
13  const rest = subsets(nums.slice(1)); // Tree: branch where first excluded
14  const withFirst = rest.map(s => [first, ...s]); // Branch with first included
15  return [...rest, ...withFirst];
16}
17
18// TAIL RECURSION — With accumulator
19function factorialTail(n: number, acc: number = 1): number {
20  if (n <= 1) return acc;
21  return factorialTail(n - 1, n * acc); // Tail position — nothing after
22}
23
24function sumArrayTail(arr: number[], idx: number = 0, acc: number = 0): number {
25  if (idx >= arr.length) return acc;
26  return sumArrayTail(arr, idx + 1, acc + arr[idx]); // Tail position
27}
28
29function fibTail(n: number, a: number = 0, b: number = 1): number {
30  if (n === 0) return a;
31  return fibTail(n - 1, b, a + b); // Tail position!
32}
33
34// MUTUAL RECURSION
35function isEven(n: number): boolean {
36  if (n === 0) return true;
37  return isOdd(n - 1);
38}
39function isOdd(n: number): boolean {
40  if (n === 0) return false;
41  return isEven(n - 1);
42}
43
44// CONVERTING TREE RECURSION TO ITERATIVE
45// Recursive DFS
46function dfsRecursive(root: TreeNode | null, result: number[] = []): number[] {
47  if (!root) return result;
48  result.push(root.val);
49  dfsRecursive(root.left, result);
50  dfsRecursive(root.right, result);
51  return result;
52}
53
54// Iterative DFS with explicit stack
55function dfsIterative(root: TreeNode | null): number[] {
56  if (!root) return [];
57  const stack: TreeNode[] = [root];
58  const result: number[] = [];
59  while (stack.length) {
60    const node = stack.pop()!;
61    result.push(node.val);
62    if (node.right) stack.push(node.right);
63    if (node.left) stack.push(node.left);
64  }
65  return result;
66}
67
68// TRAMPOLINE — Simulate TCO in JavaScript
69function trampoline(fn: Function) {
70  return function(...args: any[]) {
71    let result = fn(...args);
72    while (typeof result === 'function') {
73      result = result();
74    }
75    return result;
76  };
77}
78
79const factTrampoline = trampoline(function fact(n: number, acc = 1): any {
80  if (n <= 1) return acc;
81  return () => fact(n - 1, n * acc); // Return thunk instead of recursing
82});
83console.log(factTrampoline(100000)); // No stack overflow!

🏋️ Practice Exercise

Practice Problems:

Convert factorial to tail-recursive form with accumulator
Convert fibonacci to tail-recursive form
Write tree recursion to generate all permutations
Convert recursive tree traversal to iterative with explicit stack
Implement a trampoline function to avoid stack overflow
Write mutual recursion for an is-even checker
Count nodes in a binary tree using tree recursion
Implement flatten(nested_list) using both recursive and iterative approaches
Write a recursive function to generate Sierpinski triangle pattern
Compare stack depth of linear vs tree recursion for the same problem

⚠️ Common Mistakes

Not adding accumulator parameter for tail recursion — the result must be carried as an argument
Relying on TCO in JavaScript — only Safari supports it; use iteration or trampoline for production
Not recognizing tree recursion's exponential nature — always check if memoization is needed
Writing 'fake' tail recursion where work happens after the call — n * factorial(n-1) is NOT tail recursive
Using recursion for very deep problems without considering stack limits — convert to iterative

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Advanced Recursion (Tree Recursion, Tail Call Optimization)

Was this topic helpful?

← PreviousMemoization vs Tabulation — Deep Comparison Next →Binary Trees — Traversals & Core Operations