Recursion — thinking in terms of subproblems

Every recursive function needs two things:

1. A base case — a small input you can answer directly.
2. A recursive case — how the answer to your input is built from the answer to a smaller input.

If you can articulate #2 in one English sentence, coding is easy.

The three shapes of recursion in interviews

Linear (one recursive call)

Reduces the problem by one step each call. Depth = n. Space = O(n).

• Factorial, string reverse, list traversal

Divide-and-conquer (two or more recursive calls)

Splits the problem in half. Depth = log n. Total work = f(n) depending on how you combine.

• Merge sort, quicksort
• Binary tree traversals
• Fast exponentiation

Backtracking (recursive with undo)

Try a choice, recurse, then undo the choice. Explore all possibilities.

• Generate all permutations / subsets
• N-Queens
• Sudoku solver

The mental model

Think of each recursive call as a stack frame. Python's default recursion limit is 1000 — hit that and you get RecursionError. Use sys.setrecursionlimit(10_000) if you're deliberately deep, or rewrite iteratively.

Recursion → iteration

Any recursion can be rewritten with an explicit stack. Sometimes it's cleaner. Often it's uglier. Interviewers usually accept either.

The memoization win

If your recursion computes the same subproblem twice, add @lru_cache from functools. Fib goes from O(2ⁿ) to O(n). This trick is the foundation of dynamic programming.

Try it

1. Write a recursive function to compute the number of ways to climb n stairs, taking 1 or 2 steps at a time.
2. Rewrite it iteratively using a rolling pair of variables. Compare the space.