Recursion: Patterns, Complexity & Interview Use Cases

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller subproblems of the same type.

Why This Matters in Interviews

Recursion is essential because:

• Problem decomposition: Many problems are naturally recursive (trees, graphs, divide-and-conquer)
• Elegant solutions: Recursive solutions are often cleaner and easier to understand
• Foundation for DP: Dynamic programming builds on recursive thinking
• Algorithm design: Many algorithms use recursion (merge sort, quick sort, tree traversal)

Interviewers test recursion to assess your ability to think recursively, handle base cases, and optimize recursive solutions.

Core Concepts

• Base case: Condition that stops recursion
• Recursive case: Function calls itself with smaller input
• Call stack: Stack of function calls during execution
• Stack overflow: When recursion depth exceeds stack limit
• Tail recursion: Recursive call is last operation (can be optimized)
• Memoization: Caching results to avoid redundant calculations
• Backtracking: Recursive exploration with undo operations

Detailed Explanation

Recursion Structure

1function recursiveFunction(input: any): any {
2  // Base case: stop recursion
3  if (baseCaseCondition(input)) {
4    return baseCaseValue;
5  }
6  
7  // Recursive case: solve smaller subproblem
8  const smallerInput = reduceInput(input);
9  const result = recursiveFunction(smallerInput);
10  
11  // Combine result
12  return combine(input, result);
13}

Factorial

1function factorial(n: number): number {
2  // Base case
3  if (n <= 1) {
4    return 1;
5  }
6  
7  // Recursive case
8  return n * factorial(n - 1);
9}
10
11// Time: O(n)
12// Space: O(n) - call stack

Fibonacci

Naive recursive:

1function fibonacci(n: number): number {
2  if (n <= 1) {
3    return n;
4  }
5  
6  return fibonacci(n - 1) + fibonacci(n - 2);
7}
8
9// Time: O(2^n) - exponential!
10// Space: O(n) - call stack

Memoized:

1function fibonacciMemo(n: number, memo: Map<number, number> = new Map()): number {
2  if (n <= 1) {
3    return n;
4  }
5  
6  if (memo.has(n)) {
7    return memo.get(n)!;
8  }
9  
10  const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n -  memo

Iterative (optimal):

1function fibonacciIterative(n: number): number {
2  if (n <= 1) return n;
3  
4  let prev = 0;
5  let curr = 1;
6  
7  for (let i = 2; i <= n; i++) {
8    const next = prev + curr;
9    prev = curr;
10    curr = next;
11  }
12  
13  return curr;
14}
15
16// Time: O(n)
17// Space: O(1)

Tail Recursion

1// Not tail recursive (multiplication after recursive call)
2function factorial(n: number): number {
3  if (n <= 1) return 1;
4  return n * factorial(n - 1); // Multiplication after call
5}
6
7// Tail recursive (recursive call is last operation)
8function factorialTail(n: number, acc: number = 1): number {
9  if (n <= 1) return acc;
10  return factorialTail(n - 1, n  acc

Examples

Tower of Hanoi

1function towerOfHanoi(n: number, from: string, to: string, aux: string): void {
2  if (n === 1) {
3    console.log(`Move disk 1 from ${from} to ${to}`);
4    return;
5  }
6  
7  // Move n-1 disks from source to auxiliary
8  towerOfHanoi(n - 1, from, aux, to);

Power Function

1function power(base: number, exponent: number): number {
2  if (exponent === 0) {
3    return 1;
4  }
5  
6  if (exponent < 0) {
7    return 1 / power(base, -exponent);
8  }
9  
10  // Optimized: x^n = (x^(n/2))^2 if n is even
11  if (exponent % 2 === 0) {
12    const half = power(base, exponent / 2);

Permutations

1function permutations(nums: number[]): number[][] {
2  const result: number[][] = [];
3  
4  function backtrack(current: number[], remaining: number[]): void {
5    // Base case: no more elements
6    if (remaining.length === 0) {
7      result.push([...current]);
8      return

Common Pitfalls

• Missing base case: Infinite recursion, stack overflow. Fix: Always define base case first
• Not reducing problem size: Infinite recursion. Fix: Ensure recursive call uses smaller input
• Stack overflow: Deep recursion exceeds stack limit. Fix: Use iterative or tail recursion
• Redundant calculations: Same subproblems computed multiple times. Fix: Use memoization
• Not handling edge cases: Empty input, single element. Fix: Add explicit checks
• Mutating shared state: Side effects in recursive calls. Fix: Pass copies, avoid mutations

Interview Questions

Beginner

Q: Explain recursion. What are the key components of a recursive function?

A:

Recursion is when a function calls itself to solve a problem.

Key Components:

1. Base Case:

   • Condition that stops recursion
   • Returns a value without further recursion
   • Prevents infinite recursion

2. Recursive Case:

   • Function calls itself
   • With smaller or simpler input
   • Progresses toward base case

Example:

function factorial(n: number): number {
  // Base case
  if (n <= 1) {
    return 1;
  }
  
  // Recursive case
  return n * factorial(n - 1);
}

Call Stack:

factorial(4)
  → factorial(3)
    → factorial(2)
      → factorial(1) → returns 1
    → returns 2 * 1 = 2
  → returns 3 * 2 = 6
→ returns 4 * 6 = 24

Key points:

• Must have base case
• Must reduce problem size
• Each call uses stack space

Intermediate

Q: Compare recursive and iterative solutions. When would you use each, and how do you convert between them?

A:

Recursive vs Iterative:

When to use:

• Recursive: Tree traversal, divide-and-conquer, backtracking, naturally recursive problems
• Iterative: Simple loops, performance critical, deep recursion risk

Conversion Example:

Recursive:

function sumRecursive(n: number): number {
  if (n <= 0) return 0;
  return n + sumRecursive(n - 1);
}

Iterative:

function sumIterative(n: number): number {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

Using stack (for complex cases):

function sumWithStack(n: number): number {
  const stack: number[] = [n];
  let sum = 0;
  
  while (stack.length > 0) {
    const current = stack.pop()!;
    if (current <= 0) {
      continue;
    }
    sum += current;
    stack.push(current - 1);
  }
  
  return sum;
}

Senior

*Q: Design a recursive system for evaluating mathematical expressions with parentheses, operators (+, -, , /), and handling operator precedence. How do you optimize for performance and handle errors?

A:

class ExpressionEvaluator {
  private operators: Map<string, number> = new Map([
    ['+', 1],
    ['-', 1],
    ['*', 2],
    ['/', 2]
  ]);
  
  evaluate(expression: string): number {
    // Remove whitespace
    const cleaned = expression.replace(/\s/g, '');
    return this.evaluateRecursive(cleaned, 0, cleaned.length);
  }
  
  private evaluateRecursive(expr: string, start: number, end: number): number {
    // Base case: single number
    if (this.isNumber(expr, start, end)) {
      return parseFloat(expr.substring(start, end));
    }
    
    // Handle parentheses
    if (expr[start] === '(') {
      const closing = this.findMatchingParen(expr, start);
      const innerValue = this.evaluateRecursive(expr, start + 1, closing);
      
      if (closing + 1 >= end) {
        return innerValue;
      }
      
      // Continue with remaining expression
      return this.applyOperator(
        innerValue,
        expr[closing + 1],
        this.evaluateRecursive(expr, closing + 2, end)
      );
    }
    
    // Find operator with lowest precedence (evaluate last)
    const opIndex = this.findLowestPrecedenceOperator(expr, start, end);
    
    if (opIndex === -1) {
      throw new Error('Invalid expression');
    }
    
    const left = this.evaluateRecursive(expr, start, opIndex);
    const right = this.evaluateRecursive(expr, opIndex + 1, end);
    
    return this.applyOperator(left, expr[opIndex], right);
  }
  
  private findLowestPrecedenceOperator(expr: string, start: number, end: number): number {
    let lowestOp = -1;
    let lowestPrec = Infinity;
    let parenDepth = 0;
    
    for (let i = start; i < end; i++) {
      if (expr[i] === '(') parenDepth++;
      else if (expr[i] === ')') parenDepth--;
      else if (parenDepth === 0 && this.operators.has(expr[i])) {
        const prec = this.operators.get(expr[i])!;
        if (prec <= lowestPrec) {
          lowestPrec = prec;
          lowestOp = i;
        }
      }
    }
    
    return lowestOp;
  }
  
  private findMatchingParen(expr: string, start: number): number {
    let depth = 1;
    for (let i = start + 1; i < expr.length; i++) {
      if (expr[i] === '(') depth++;
      else if (expr[i] === ')') {
        depth--;
        if (depth === 0) return i;
      }
    }
    throw new Error('Unmatched parenthesis');
  }
  
  private applyOperator(left: number, op: string, right: number): number {
    switch (op) {
      case '+': return left + right;
      case '-': return left - right;
      case '*': return left * right;
      case '/': 
        if (right === 0) throw new Error('Division by zero');
        return left / right;
      default: throw new Error(`Unknown operator: ${op}`);
    }
  }
  
  private isNumber(expr: string, start: number, end: number): boolean {
    const numStr = expr.substring(start, end);
    return /^-?\d+(\.\d+)?$/.test(numStr);
  }
}

// Usage
const evaluator = new ExpressionEvaluator();
console.log(evaluator.evaluate("2 + 3 * 4")); // 14
console.log(evaluator.evaluate("(2 + 3) * 4")); // 20
console.log(evaluator.evaluate("2 * 3 + 4 / 2")); // 8

// Optimization: Memoization for repeated subexpressions
class OptimizedEvaluator extends ExpressionEvaluator {
  private memo: Map<string, number> = new Map();
  
  evaluate(expression: string): number {
    this.memo.clear();
    return super.evaluate(expression);
  }
  
  protected evaluateRecursive(expr: string, start: number, end: number): number {
    const key = `${start}-${end}`;
    if (this.memo.has(key)) {
      return this.memo.get(key)!;
    }
    
    const result = super.evaluateRecursive(expr, start, end);
    this.memo.set(key, result);
    return result;
  }
}

Features:

1. Recursive parsing: Handles nested parentheses
2. Operator precedence: Evaluates in correct order
3. Error handling: Division by zero, unmatched parentheses
4. Memoization: Caches subexpression results
5. Optimization: Avoids redundant calculations

• Recursion: Function calls itself to solve subproblems

• Base case: Essential to stop recursion

• Call stack: Understand stack growth and limits

• Memoization: Cache results to avoid redundant calculations

• Tail recursion: Can be optimized to iterative

• When to use: Natural for trees, graphs, divide-and-conquer

• Optimization: Convert to iterative or use memoization for performance

• Dynamic Programming - DP builds on recursive thinking with memoization

• Backtracking - Recursive exploration with undo operations

• Tree Traversal - Recursive algorithms for tree problems

• Graph Traversal - DFS uses recursion naturally

• Arrays - Understanding arrays before recursive array problems