Recursion explained for students
7 min readUpdated
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. It appears in school courses, university modules and coding interviews, and it is one of the topics students find hardest to trace on paper.
The two parts of every recursive function
- Base case: the smallest input, answered directly without another call. Without it the function never stops.
- Recursive case: the function calls itself on a smaller input and uses that answer to build its own.
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(4)) # 24Tracing a recursive call
Each call waits for the call below it to return. Write the calls going down, then the answers coming back up.
| Call | Waits for | Returns |
|---|---|---|
| factorial(4) | 4 * factorial(3) | 24 |
| factorial(3) | 3 * factorial(2) | 6 |
| factorial(2) | 2 * factorial(1) | 2 |
| factorial(1) | nothing (base case) | 1 |
The call stack
The computer keeps every waiting call on the call stack. Each call adds a frame; each return removes one. Very deep recursion can fill the stack and stop the program with a stack overflow (in Python, a RecursionError).
Common mistakes
- Forgetting the base case, or writing one the input never reaches.
- Not making the input smaller in the recursive call.
- Forgetting to
returnthe result of the recursive call. - Using recursion where a simple loop is clearer and safer.
Recursion or a loop?
Anything recursive can be written with a loop. Recursion is clearer for problems that split into smaller copies of themselves, such as tree traversal, merge sort and backtracking. Loops are usually better for simple counting and running totals.
Frequently asked questions
What is a base case in recursion?
The base case is the input small enough to answer without another recursive call, such as n <= 1 for factorial. It stops the recursion.
Why does my recursive function never stop?
Either the base case is missing, or the recursive call does not move the input towards it. Check that each call uses a smaller input.
Is recursion slower than a loop?
Often slightly, because each call adds a stack frame. For most school and university problems the difference does not matter; clarity matters more.
Learn it step by step
Practise this, step by step
Short lessons with quizzes, practice and interview questions, from your first program to job-ready.