Recursion
Recursion is a technique where a function calls itself to solve a smaller instance of the same problem. Every recursive solution has two parts: a base case...
What is Recursion?
Recursion is a technique where a function calls itself to solve a smaller instance of the same problem. Every recursive solution has two parts: a base case that stops the recursion by returning a value directly, and a recursive case that breaks the problem into a simpler subproblem and calls the function again. Without a base case, recursion continues forever until Python raises RecursionError (maximum recursion depth exceeded, default 1000 frames).
Classic Example: Factorial
The factorial of n (written n!) is defined as n * (n-1) * ... * 1, with 0! = 1. Recursive implementation: def factorial(n): if n == 0: return 1; return n * factorial(n - 1). Tracing factorial(4): 4 * factorial(3) → 4 * 3 * factorial(2) → 4 * 3 * 2 * factorial(1) → 4 * 3 * 2 * 1 * factorial(0) → 4 * 3 * 2 * 1 * 1 = 24. The base case n == 0 returns 1, unwinding the chain.
Call Stack Behaviour
Each recursive call adds a new frame to the call stack. The stack grows until the base case is reached, then frames are popped in reverse order, computing the result at each level. Python's default recursion limit is 1000, set to prevent stack overflow. You can inspect it with sys.getrecursionlimit() and increase it with sys.setrecursionlimit(n), though doing so for production code is usually a sign that an iterative approach would be better.
Recursive vs Iterative Solutions
Most recursive solutions have an equivalent iterative version. Recursion can be more elegant and closer to the mathematical definition of a problem (like tree traversal or divide-and-conquer algorithms), but iteration is usually faster and uses less memory because it does not add frames to the call stack. For very deep recursion (thousands of levels), Python's stack limit becomes a constraint. Functional languages like Haskell use tail-call optimization to handle this; standard CPython does not.
Fibonacci with Memoization
The naive recursive Fibonacci has exponential time complexity because it recalculates the same values repeatedly. fib(5) calls fib(4) and fib(3); fib(4) also calls fib(3), and so on. Memoization caches results: from functools import lru_cache; @lru_cache(maxsize=None); def fib(n): if n < 2: return n; return fib(n-1) + fib(n-2). With lru_cache, each unique n is computed only once, making the time complexity linear (O(n)).
Exam Tip
Recursion exam questions typically ask you to trace through a small example or identify a missing base case. Always write out the call tree for small inputs when tracing. Common trick: what happens if the base case is never reached? RecursionError is raised after the default limit of 1000 frames. Also know that Python does not support tail-call optimization, so deep recursion will hit the limit even if written in tail-recursive style. For those cases, convert to a loop or use an explicit stack.