Structural Decomposition — Recursion

Recursion is not magic. It is structural decomposition.

If a problem looks like a smaller version of itself, recursion is often the cleanest model.

🧠 Why Recursion Feels Hard

Because you cannot "see" the stack.

Iteration feels mechanical. Recursion feels abstract.

The fear is not recursion. The fear is invisible memory growth.

🔍 What Recursion Actually Is

A function that solves a problem by delegating to a smaller instance of the same problem.

• A base case (when to stop)
• A smaller subproblem
• A structural invariant

Without a base case → infinite recursion → stack overflow.

Simple Example — Factorial

function factorial(n: number): number {
  if (n === 0) return 1
  return n * factorial(n - 1)
}

Time: O(n)

Space: O(n)

Depth equals memory growth.

⚠️ Where Recursion Breaks — Fibonacci

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

Time: O(2ⁿ)

The issue is not recursion. The issue is repeated subproblems.

🧱 Structural Fix — Memoization

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

  const value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo)
  memo.set(n, value)

  return value
}

Time: O(n)

Space: O(n)

Memoization transforms exponential growth into linear growth — this is a structural shift, not a trick.

🧠 State & Transitions

Many recursive problems are not about calling a function again. They are about defining state correctly.

State is the minimal information needed to describe where you are in the problem.

• In Fibonacci → state is n
• In tree traversal → state is the current node
• In backtracking → state is the partial solution

Once state is defined clearly, transitions become mechanical.

Most recursion mistakes come from unclear state definition, not from the recursion itself.

🌳 Trees — Where Recursion Feels Natural

Trees are recursively defined structures.

Each subtree is itself a tree. Recursion mirrors the structure itself.

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null

  const temp = root.left
  root.left = root.right
  root.right = temp

  invertTree(root.left)
  invertTree(root.right)

  return root
}

Time: O(n)

Space: O(h)

⚖️ Recursion vs Iteration

• Recursive → clearer structural expression
• Iterative → explicit memory control

Clarity and control are trade-offs. Choose deliberately.

🧭 Panic Reset Strategy

• Is this problem structurally self-similar?
• What is the base case?
• What exactly is my state?
• How does state transition to the next step?
• Am I recomputing subproblems?

🧠 Mental Model Summary

• Recursion expresses structural self-similarity.
• Stack depth equals memory growth.
• Repeated subproblems create explosions.
• Memoization trades memory for time.
• Clear state definition prevents confusion.

Final Insight

Recursion is not about cleverness.

It is about expressing structure clearly and defining state precisely.