Recursion and Recurrence

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. It’s like looking into parallel mirrors: the image repeats infinitely, getting smaller each time.

But unlike mirrors, a recursive function must stop eventually.

1. Anatomy of a Recursive Function

Every recursive function needs two parts:

  1. Base Case: The condition where the recursion stops (e.g., if (n == 0) return 1). Without this, you get infinite recursion (Stack Overflow).
  2. Recursive Step: The part where the function calls itself with a modified argument (e.g., return n * factorial(n - 1)).

Example: Factorial

Factorial of n (written n!) is n * (n-1) * (n-2) * ... * 1.

Java Implementation

public int factorial(int n) {
  if (n <= 1) return 1;       // Base Case
  return n * factorial(n - 1); // Recursive Step
}

Go Implementation

func Factorial(n int) int {
  if n <= 1 {
    return 1
  }
  return n * Factorial(n - 1)
}

2. The Call Stack

When a function calls itself, the computer pauses the current function and pushes a new Stack Frame onto the Call Stack. This frame holds the local variables and return address. When the called function returns, its frame is popped off, and the previous function resumes.

Interactive Call Stack Visualizer

Watch how the stack grows and shrinks for factorial(3).

Stack is empty
Click Step to start factorial(3)...

3. Recurrence Relations

How do we calculate the time complexity of a recursive function? We use a Recurrence Relation: an equation that describes the function in terms of itself.

For factorial(n):

  • Time needed: T(n)
  • Work done: One multiplication + recursive call T(n-1)
  • Equation: T(n) = T(n-1) + O(1)

Solving this (by substitution): T(n) = T(n-1) + 1 ` = (T(n-2) + 1) + 1 = T(n-2) + 2 … = T(n-k) + k When k=n, T(0) = O(1), so T(n) = O(n)`.

This tells us factorial is O(n) time complexity.

[!WARNING] Deep recursion can cause Stack Overflow Errors if the recursion depth exceeds the stack size limit (usually a few thousand frames).

Next Steps

Recursion is elegant but risky. Is there a safer way? Let’s compare Iterative vs. Recursive approaches.

4. Deep Dive Strategy Lab: Recursion And Recurrence

Intuition Through Analogy

Think of this chapter like debugging a production outage timeline. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?