Recursion is the topic where many students first feel lost in DSA: a function that calls itself? Won't it go on forever? The good news is that recursion follows just three rules, and once you can see the call stack, it stops being mysterious.
Recursion is also the key that unlocks the rest of this course: merge sort, trees, graph search (DFS) and dynamic programming all use it. This guide gives you a live call stack to step through, the classic examples, recursion vs iteration, and a memory trick from a dark cinema hall.
What is recursion?
Recursion means defining something in terms of a smaller version of itself. You already know examples from maths:
5! = 5 × 4!, and4! = 4 × 3!, … down to1! = 1.- The sum of 1 to n is
n + (sum of 1 to n − 1), and the sum of nothing is 0.
In code, that becomes a function that calls itself with a smaller argument. Every correct recursive function has the same three parts:
- Base case: the smallest input, answered directly. This is what stops the recursion.
- Recursive call on a smaller input: n − 1, the rest of the list, half the array, a child node.
- Combine: use the returned answer to build this call's answer (
n × fact(n − 1)).
How recursion works: the call stack
When a function calls another function (even itself), the caller pauses and a new stack frame is pushed onto the call stack. Picture a pile of plates: the last frame added is the first one to finish (you'll study this stack structure properly in part 6). Step through fact(n) and watch frames pile up until the base case, then unwind:
🎮 Watch the call stack
def fact(n):
if n <= 1: # base case
return 1
return n * fact(n - 1) # recursive case
print(fact(4))Call stack (top = running now)
Step 1 of 8. fact(4) can't answer yet. It needs fact(3), so it pauses and calls it. A new frame is pushed on the call stack.
🧠 PATH memory card
Remember recursion for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
You're in the last row of a dark cinema and can't see row numbers. You ask the person in front “which row are you in?”. They ask the person in front of them… until row 1 says “1”. Then each person adds 1 and passes it back. You learn you're in row 5.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Base STOPS, Call SHRINKS, Return BUILDS”
- Row 1 just knows→Base case: answered directly, no more calls
- Base STOPS→Without a base case: infinite calls, stack overflow
- Ask the row in front→The recursive call
- Call SHRINKS→Each call is closer to the base (row − 1)
- Answer + 1→Combine the returned value
- Return BUILDS→The final answer is built on the way back
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
row(5)asksrow(4)→row(3)→row(2)→row(1), which returns 1 (base). Then back up: 1 + 1 = 2, 2 + 1 = 3, 3 + 1 = 4, 4 + 1 = 5. Four calls down, four answers up. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 9 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Recursion examples in Python, Java and C++
Four classics: factorial, sum of digits, reversing a string, and fast power (which halves the problem each time, so it runs in O(log n), the same idea as binary search).
def factorial(n):
if n <= 1: # 1. base case: STOP
return 1
return n * factorial(n - 1) # 2. call on a SMALLER input, 3. BUILD the answer
def sum_digits(n): # 1234 -> 1 + 2 + 3 + 4 = 10
if n < 10:
return n
return n % 10 + sum_digits(n // 10)
def reverse(s): # "chai" -> "iahc"
if len(s) <= 1:
return s
return reverse(s[1:]) + s[0]
def power(x, n): # x^n in O(log n): divide and conquer
if n == 0:
return 1
half = power(x, n // 2)
return half * half if n % 2 == 0 else half * half * x
print(factorial(5)) # 120
print(sum_digits(1234)) # 10
print(reverse("chai")) # iahc
print(power(2, 10)) # 1024When recursion repeats itself: Fibonacci
Fibonacci is defined recursively: fib(n) = fib(n − 1) + fib(n − 2), with fib(0) = 0 and fib(1) = 1. Translate that straight into code and it works, but look at all the calls it makes:
🌳 Every call fib(5) makes (15 calls!)
The same sub-problems are solved again and again. For fib(40) this naive recursion makes over 300 million calls. Remembering answers instead of recomputing them is exactly what dynamic programming does.
Each call makes two more calls, so the work roughly doubles with every +1 to n: about O(2ⁿ). This is the most famous example of recursion done naively, and the doorway to dynamic programming, the final part of this course.
Recursion vs iteration
| Feature | Recursion | Iteration |
|---|---|---|
| How it repeats | Function calls itself | A loop (for / while) |
| Stops when | Base case is reached | Loop condition becomes false |
| Extra memory | O(depth) call stack frames | Usually O(1) |
| Risk | Stack overflow if too deep | Infinite loop if condition is wrong |
| Best for | Trees, graphs, divide & conquer, backtracking | Simple counting and repetition |
| Readability | Short and close to the maths | More explicit steps |
Python stops recursion at about 1,000 levels by default, so for very deep inputs a loop is safer. For trees and graphs, recursion is usually the clearest choice.
How to write any recursive function
- Trust the call. Assume
f(smaller)already works. Don't trace every level in your head. - Find the base case: the input so small the answer is obvious (0, 1, empty list, NULL node).
- Shrink: decide how to make the problem smaller.
- Build: combine the smaller answer into this answer.
What to learn next
You're ready for the next part of the course: sorting algorithms. Merge sort and quick sort are recursive (split the problem, solve the halves, combine), so they'll make sense straight away. Later, recursion is how you'll walk trees and explore graphs with DFS.
Key takeaways
- ✓Recursion: a function solves a problem by calling itself on a smaller input.
- ✓Every recursive function needs a base case, a shrinking call, and a way to combine results.
- ✓Calls are tracked on the call stack, so recursion uses O(depth) extra memory.
- ✓No base case or no shrinking means stack overflow.
- ✓Naive recursive Fibonacci repeats work (O(2ⁿ)); dynamic programming fixes it.
- ✓Remember it with “Base STOPS, Call SHRINKS, Return BUILDS.”
Frequently asked questions
What is recursion in simple words?
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem, until it reaches a version so small it can answer directly (the base case). The answers then combine on the way back up.
What is a base case and why is it necessary?
The base case is the condition where the function returns an answer without calling itself again, such as n <= 1 for factorial. Without it, the function calls itself forever, the call stack fills up, and the program crashes with a stack overflow (RecursionError in Python, StackOverflowError in Java).
How does recursion use the call stack?
Every function call gets a stack frame holding its arguments and local variables. When a function calls itself, a new frame is pushed on top and the caller waits. When the base case returns, frames are popped one by one, each finishing its work with the returned value. The deepest the stack gets is the recursion's extra space.
Is recursion better than iteration (loops)?
Neither is always better. Recursion is clearer for problems that are naturally self-similar: trees, graphs, divide and conquer (merge sort, quick sort) and backtracking. Loops use less memory and avoid stack overflow for simple repetition. Any recursion can be rewritten with a loop and an explicit stack.
What is tail recursion?
A recursive call is a tail call when it is the very last thing the function does, with nothing left to compute after it returns. Some languages and compilers can turn tail recursion into a loop so it uses O(1) stack space. Python and Java do not do this optimisation, so deep recursion can still overflow there.
🧠 Quick check: recursion
1. What happens if a recursive function has no base case?
2. What does sum(3) return if sum(n) = n + sum(n − 1) and sum(0) = 0?
3. How much extra space does recursive factorial(n) use?
4. In “Base STOPS, Call SHRINKS, Return BUILDS”, what does “Call SHRINKS” mean?
Checking your access…