What Is Recursion?
Recursion is when a function calls itself. That sounds circular, but it works because each call tackles a smaller version of the same problem until it hits a stopping point.
Every recursive function has exactly two parts:
- Base case — the condition that stops the recursion. Without it, you get infinite calls and a
RecursionError. - Recursive case — the function calls itself with a smaller or simpler input, moving toward the base case.
Open a doll and there is a smaller one inside. Keep opening until you reach the tiniest doll that doesn't open — that's the base case. Then you close them back up one by one — that's the return phase.
Call Stack Visualization
When a function calls itself, Python pushes a new frame onto the call stack. Each frame waits for the one above it to finish. Once the base case returns, the stack unwinds — each frame completes in reverse order.
factorial(4) — Building the Stack
Unwinding — Returns Cascade Back
Factorial
The classic first recursion example. n! equals n * (n-1)!, and 1! = 1 (or 0! = 1). That definition is already recursive.
Space complexity: O(n) — n frames on the call stack at the deepest point.
Fibonacci — Naive vs Memoized
The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, ... where each number is the sum of the two before it. The naive recursive solution is elegant but dangerously slow.
Naive: O(2^n) — very slow!
fib(5) calls fib(3) twice, fib(2) three times. The same subproblems get recomputed over and over. The number of calls doubles with each increase in n.
Memoized: O(n) — fast!
Store each result the first time you compute it. If you see the same input again, return the cached value instantly.
Fibonacci Recursion Tree
This diagram shows why naive Fibonacci is O(2^n). Each node is a function call. Orange nodes are overlapping subproblems — work that gets repeated. Memoization eliminates all of them.
fib(5) Recursion Tree — Overlapping Subproblems in Orange
Recursion vs Iteration
Any recursive solution can be rewritten iteratively and vice versa. The question is: which is clearer and more efficient for your specific problem?
| Aspect | Recursion | Iteration |
|---|---|---|
| Readability | Elegant for tree/graph traversal, divide & conquer | Straightforward for linear tasks (summing, counting) |
| Space | O(n) call stack (can cause stack overflow) | O(1) for simple loops |
| Speed | Function call overhead per frame | Generally faster in tight loops |
| Best for | Trees, graphs, backtracking, nested structures | Arrays, linked list traversal, counting |
| Danger zone | Missing base case = infinite recursion | Wrong loop condition = infinite loop |
sys.setrecursionlimit(). In interviews, mention this trade-off.
Problem: Power of Two
Given an integer n, determine if it is a power of two. Think recursively: if n is even, keep dividing by 2. If you reach 1, it is a power of two. If you reach an odd number or something less than 1, it is not.
Problem: Flatten Nested List
Given an arbitrarily nested list, return a flat list of all the values. This is a natural fit for recursion because the nesting depth is unknown — you can't solve it with a fixed number of loops.
Try It Yourself
Fibonacci: Naive vs Memoized Timing
Run both versions and see the difference. The naive version gets painfully slow at n=35; the memoized version handles n=500 instantly.
Challenge
Write a recursive function digit_sum(n) that returns the sum of all digits in a non-negative integer. For example, digit_sum(1234) should return 10 (1+2+3+4). The function should keep calling itself, peeling off one digit at a time.
Test cases:
digit_sum(1234)should return10digit_sum(9999)should return36digit_sum(0)should return0digit_sum(5)should return5
n % 10 to get the last digit and n // 10 to remove it. Your base case is when n == 0. The recursive formula is: digit_sum(n) = (n % 10) + digit_sum(n // 10).
Quiz
You've mastered recursion.
Now conquer the full interview.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →