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.
🪞
Think of it this way
Russian nesting dolls

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.

Interview tip: When an interviewer says "solve this recursively," they want you to identify (1) the base case, (2) how to break the problem into a smaller subproblem, and (3) how to combine the results.

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

Call 1
factorial(4) → 4 * factorial(3)
Call 2
factorial(3) → 3 * factorial(2)
factorial(4) waiting...
Call 3
factorial(2) → 2 * factorial(1)
factorial(3) waiting...
factorial(4) waiting...
Base case
factorial(1) → returns 1
factorial(2) waiting...
factorial(3) waiting...
factorial(4) waiting...

Unwinding — Returns Cascade Back

Return 1
factorial(1) returns 1
Return 2
factorial(2) returns 2 * 1 = 2
Return 3
factorial(3) returns 3 * 2 = 6
Final
factorial(4) returns 4 * 6 = 24

Factorial

The classic first recursion example. n! equals n * (n-1)!, and 1! = 1 (or 0! = 1). That definition is already recursive.

factorial.py Base case + recursive case
Output
120 1 1 3628800
Time complexity: O(n) — one call per number from n down to 1.
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_naive.py Exponential time — each call spawns two more
Output
55
Why is naive fib so 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.

fib_memo.py Linear time with memoization
Output
55 12586269025 354224848179261915075
Interview insight: This pattern — recursion + memoization — is called top-down dynamic programming. You'll see it constantly in DP problems. The key idea: "Don't recompute what you've already solved."

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

f(5) f(4) f(3) f(3) f(2) f(2) f(1) f(2) f(1) f(1) f(0) f(1) f(0) f(1) f(0) Unique call Overlapping (repeated)

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
Python's recursion limit is 1000 by default. For problems with deep recursion (e.g., n > 900), prefer iteration or increase the limit with 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.

power_of_two.py Recursive halving
Output
True True True False False
Complexity: O(log n) time and space — you halve the input at each step, so the depth is log2(n).

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.

flatten.py Recursive flattening
Output
[1, 2, 3, 4, 5, 6] [1, 2, 3, 4, 5, 6] [1, 2, 3]
Pattern: "If the item is simple, process it. If it's complex (a list), recurse." This same pattern appears in tree traversal, JSON parsing, and file-system walks.

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

Recursive Sum of Digits
Your task

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 return 10
  • digit_sum(9999) should return 36
  • digit_sum(0) should return 0
  • digit_sum(5) should return 5
Use 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

Question 1 of 5
What are the two essential parts of every recursive function?
Question 2 of 5
What is the time complexity of naive recursive Fibonacci?
Question 3 of 5
Why does memoization speed up recursive Fibonacci from O(2^n) to O(n)?
Question 4 of 5
What happens if a recursive function has no base case?
Question 5 of 5
In the flatten nested list problem, what determines whether to recurse or append?
0
/5
Great work! You understand recursion.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →