Recursion Concept and Call Stack Visualization in DSA Typescript

Mental Model

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case it can solve directly.

Analogy: Imagine a set of Russian nesting dolls where each doll contains a smaller doll inside. You open each doll until you find the smallest one, then close them back in reverse order.

function call stack:
main()
  ↓
func() -> func() -> func() -> base case
  ↑       ↑       ↑       ↑
 call1   call2   call3   call4

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Show how recursive calls build up and then resolve using the call stack

Step 1: Call factorial(3), which calls factorial(2)

call stack: factorial(3) ↑
factorial(2) ↑

Why: We break the problem into smaller parts by calling factorial with a smaller number

Step 2: factorial(2) calls factorial(1)

call stack: factorial(3) ↑
factorial(2) ↑
factorial(1) ↑

Why: Keep breaking down until we reach the simplest case

Step 3: factorial(1) calls factorial(0), the base case

call stack: factorial(3) ↑
factorial(2) ↑
factorial(1) ↑
factorial(0) ↑

Why: Base case stops recursion and starts returning values

Step 4: factorial(0) returns 1, factorial(1) returns 1 * 1 = 1

call stack unwinding:
factorial(3) ↑
factorial(2) ↑
factorial(1) returns 1

Why: Start resolving calls by returning results back up the stack

Step 5: factorial(2) returns 2 * 1 = 2

call stack unwinding:
factorial(3) ↑
factorial(2) returns 2

Why: Combine returned values to build the final answer

Step 6: factorial(3) returns 3 * 2 = 6, recursion ends

call stack empty, final result = 6

Why: All calls resolved, final answer is ready

Result:

call stack empty
final result = 6

Annotated Code

DSA Typescript

class Factorial {
  static factorial(n: number): number {
    if (n === 0) {
      return 1; // base case: factorial(0) = 1
    }
    return n * Factorial.factorial(n - 1); // recursive call
  }
}

// Driver code
const input = 3;
const result = Factorial.factorial(input);
console.log(`Factorial of ${input} is ${result}`);

if (n === 0) { return 1; }

Check base case to stop recursion

return n * Factorial.factorial(n - 1);

Recursive call with smaller input to build solution

Output

Factorial of 3 is 6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching the base case

Space: O(n) because each recursive call adds a new layer to the call stack

vs Alternative: Compared to a loop, recursion uses more memory due to call stack but can be simpler to write for problems naturally defined recursively

Edge Cases

Input is 0

Returns 1 immediately as base case

DSA Typescript

if (n === 0) { return 1; }

Input is 1

Calls factorial(0) then returns 1 * 1 = 1

DSA Typescript

return n * Factorial.factorial(n - 1);

When to Use This Pattern

When a problem can be broken into smaller similar problems and has a clear stopping point, use recursion to simplify the solution by calling the function within itself.

Common Mistakes

Mistake: Forgetting the base case causing infinite recursion
Fix: Always include a base case that stops recursion, like 'if (n === 0) return 1;'

Mistake: Not reducing the problem size in recursive call
Fix: Make sure each recursive call uses a smaller input, e.g., 'factorial(n - 1)'

Summary

Calculates a problem by calling itself with smaller inputs until a simple base case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems.

The key is the base case that stops recursion and the call stack that keeps track of unfinished calls.