ReviseAlgo Logo

Functions

Recursion

Functions calling themselves with base cases and memoization

Interview: Extremely common in interviews — tree traversal, divide-and-conquer, and dynamic programming

Last Updated: June 12, 2026 • 12 min read

Recursion is when a function calls itself to solve a problem by breaking it into smaller subproblems. It's a fundamental technique in computer science, especially for tree/graph traversal, divide-and-conquer algorithms, and problems with naturally recursive structure. Mastering recursion is essential for coding interviews.

Anatomy of a Recursive Function

  • Base case: The condition that stops recursion — without it, infinite recursion causes stack overflow
  • Recursive case: The function calls itself with a smaller/simpler input, moving toward the base case
  • Progress: Each recursive call must make progress toward the base case — otherwise infinite loop
  • Return: Results are combined as calls unwind from the base case back to the original call

Types of Recursion

  • Direct: Function calls itself — most common pattern
  • Mutual: Two functions call each other — is_even calls is_odd and vice versa
  • Tail recursion: Recursive call is the last operation — Python does NOT optimize this
  • Multiple recursion: Function makes more than one recursive call — Fibonacci, tree traversal

Memoization: Making Recursion Fast

Naive recursive Fibonacci is O(2^n). With memoization (caching results), it becomes O(n). Use @lru_cache from functools for automatic memoization, or pass a memo dict manually. This is the bridge between recursion and dynamic programming.

Python Recursion Limits

  • Default limit: Python's default recursion depth is ~1000 — exceeding it raises RecursionError
  • sys.setrecursionlimit(): Increase the limit, but be careful — too deep causes segfaults
  • Iterative alternative: Any recursion can be converted to iteration using an explicit stack
  • Performance: Each recursive call adds a stack frame — recursion uses O(n) memory for O(n) depth

When to Use Recursion

  • Tree/graph traversal: DFS, binary tree operations, directory walking
  • Divide-and-conquer: Merge sort, quicksort, binary search
  • Backtracking: Permutations, combinations, N-queens, maze solving
  • Mathematical: Factorial, GCD, power, Fibonacci

Stack Overflow Prevention

Always verify your base case is correct and that each recursive call moves toward it. Add a maximum depth parameter for safety: def recurse(n, depth=0, max_depth=1000). In production code, prefer iterative solutions for deep recursions.

Use Cases

Tree and graph traversal (DFS, inorder/preorder/postorder)

Divide-and-conquer algorithms (merge sort, quicksort, binary search)

Backtracking problems (permutations, combinations, N-queens)

Dynamic programming with memoization (knapsack, longest subsequence)

Processing recursively structured data (nested JSON, file systems)

Common Mistakes

Missing or incorrect base case — causes infinite recursion and RecursionError

Not making progress toward base case — each call must reduce the problem size

Ignoring Python's ~1000 recursion limit — use sys.setrecursionlimit() or convert to iteration

Not using memoization for overlapping subproblems — exponential time without it

Choosing recursion when iteration is simpler — Python doesn't optimize tail recursion