ReviseAlgo Logo

Functions

Recursion

Functions calling themselves

Interview: Very common in interviews

Recursion

Recursion is when a function calls itself to solve a smaller subproblem of the same type. Every recursive function needs a base case that terminates the chain and a recursive case that makes progress toward the base case.

Call Stack and Stack Overflow

Each recursive call pushes a new stack frame. Stack size is typically 1-8 MB. Deep recursion (millions of calls) causes a stack overflow. For deep recursion, convert to iterative with an explicit stack data structure, or use tail-call optimization.

Tail Recursion Optimization

A tail-recursive function makes the recursive call as its last operation. Some compilers (with optimization enabled) transform tail recursion into a loop (jump), reusing the same stack frame. C++ doesn't guarantee tail-call optimization (unlike Haskell or Scheme), but GCC/Clang often apply it with -O2.

Interview Corner

Q: What is memoization and how does it relate to recursion?

A: Memoization caches the results of recursive calls to avoid redundant recomputation. Fibonacci naively has O(2^n) time due to overlapping subproblems. With memoization (storing results in a hash map or array), it becomes O(n). This is the basis of top-down dynamic programming — recursion + memoization.

Q: When should you prefer iteration over recursion?

A: Prefer iteration when: (1) recursion depth is large (stack overflow risk), (2) performance is critical (function call overhead), or (3) the iterative solution is equally clear. Prefer recursion when: the problem is naturally recursive (trees, graphs, divide-and-conquer), and depth is bounded.

Common Pitfalls

  • Missing base case: Results in infinite recursion and stack overflow. Always verify every code path hits the base case.
  • Modifying shared state in recursive calls: Passing references to shared data and modifying it in recursive calls leads to subtle order-of-execution bugs.

Best Practices

  • Always identify and implement the base case first before the recursive case.
  • Add memoization for exponential-time recursion (overlapping subproblems) to achieve polynomial time.