Recursion

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

function recursiveFunction(input: any): any {
  // Base case: stop recursion
  if (baseCaseCondition(input)) {
    return baseCaseValue;
  }
  
  // Recursive case: solve smaller subproblem
  const smallerInput = reduceInput(input);
  const result = recursiveFunction(smallerInput);
  
  // Combine result
  return combine(input, result);
}

Factorial

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

// Time: O(n)
// Space: O(n) - call stack

Fibonacci

Naive recursive:

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

// Time: O(2^n) - exponential!
// Space: O(n) - call stack

Memoized:

function fibonacciMemo(n: number, memo: Map<number, number> = new Map()): number {
  if (n <= 1) {
    return n;
  }
  
  if (memo.has(n)) {
    return memo.get(n)!;
  }
  
  const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

// Time: O(n)
// Space: O(n)

Iterative (optimal):

function fibonacciIterative(n: number): number {
  if (n <= 1) return n;
  
  let prev = 0;
  let curr = 1;
  
  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  
  return curr;
}

// Time: O(n)
// Space: O(1)

Tail Recursion

// Not tail recursive (multiplication after recursive call)
function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // Multiplication after call
}

// Tail recursive (recursive call is last operation)
function factorialTail(n: number, acc: number = 1): number {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc); // Recursive call is last
}

// Can be optimized by compiler to iterative (no stack growth)

---

Examples

Tower of Hanoi

function towerOfHanoi(n: number, from: string, to: string, aux: string): void {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  
  // Move n-1 disks from source to auxiliary
  towerOfHanoi(n - 1, from, aux, to);
  
  // Move largest disk from source to destination
  console.log(`Move disk ${n} from ${from} to ${to}`);
  
  // Move n-1 disks from auxiliary to destination
  towerOfHanoi(n - 1, aux, to, from);
}

// Time: O(2^n)
// Space: O(n)

Power Function

function power(base: number, exponent: number): number {
  if (exponent === 0) {
    return 1;
  }
  
  if (exponent < 0) {
    return 1 / power(base, -exponent);
  }
  
  // Optimized: x^n = (x^(n/2))^2 if n is even
  if (exponent % 2 === 0) {
    const half = power(base, exponent / 2);
    return half * half;
  } else {
    return base * power(base, exponent - 1);
  }
}

// Time: O(log n)
// Space: O(log n)

Permutations

function permutations(nums: number[]): number[][] {
  const result: number[][] = [];
  
  function backtrack(current: number[], remaining: number[]): void {
    // Base case: no more elements
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    
    // Try each remaining element
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      const newRemaining = remaining.filter((_, idx) => idx !== i);
      backtrack(current, newRemaining);
      current.pop(); // Backtrack
    }
  }
  
  backtrack([], nums);
  return result;
}

// Time: O(n! * n)
// Space: O(n! * n)

---

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:

Feature	Recursive	Iterative
Code clarity	Often cleaner	Can be more verbose
Space	O(n) call stack	O(1) usually
Performance	Function call overhead	Direct execution
Stack overflow	Risk with deep recursion	No risk
Natural fit	Tree/graph problems	Linear problems

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

---

Key Takeaways

• 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