Recursion concepts
Understand recursion as a function calling itself on a smaller sub-problem, and learn to identify the base case and recursive case that every correct recursive function needs.
- Explain recursion as a function calling itself on a smaller sub-problem
- Identify the base case and recursive case in a recursive function
- Describe what the call stack does during recursion and why infinite recursion causes a stack overflow
Most problems you have solved so far used loops: start at one end, walk to the other, accumulate a result. Recursion is a different shape. A recursive function solves a problem by solving a slightly smaller version of the same problem and combining the result. The function calls itself — and that is not a bug, it is the entire strategy.
The canonical example: factorial
The factorial of a non-negative integer n (written n!) is defined as:
0! = 1(by definition)n! = n × (n-1)!for n > 0
That second line is recursive: "the factorial of n equals n times the factorial of n-1." In code:
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive caseEvery correct recursive function has exactly two parts:
- Base case — the condition where the function stops calling itself and returns a direct answer. Without a base case, the function recurses forever.
- Recursive case — the condition where the function calls itself with a smaller argument, moving toward the base case.
The call stack: what actually happens
When Python calls a function, it creates a stack frame — a small block of memory that stores the function's local variables and the point to return to when the function finishes. Stack frames are stacked on top of each other, hence the name "call stack."
When factorial(3) runs:
factorial(3)is called. It can't return yet — it needsfactorial(2).factorial(2)is called. It needsfactorial(1).factorial(1)is called. It needsfactorial(0).factorial(0)hits the base case and returns1.factorial(1)gets1back and returns1 × 1 = 1.factorial(2)gets1back and returns2 × 1 = 2.factorial(3)gets2back and returns3 × 2 = 6.
Each pending call waits on the stack until the one below it resolves. The stack grows as calls pile up, and shrinks as they return.
Stack overflow: what goes wrong without a base case
If you forget the base case — or write a recursive case that never gets smaller —
the function calls itself indefinitely. The call stack fills up. Python detects
this and raises a RecursionError: maximum recursion depth exceeded. In other
languages this is called a stack overflow.
The mental check before writing any recursive function: "does every possible input eventually reach the base case?" If yes, the recursion terminates. If no, you have infinite recursion waiting to happen.
Think of each recursive call as a sub-problem: "I don't know the answer directly, but if someone handed me the answer to this slightly smaller version, I could compute mine." The base case is the one problem small enough that you know the answer directly, without help.
The mental model to carry forward
Recursion is not magic — it is structured delegation. When you write
return n * factorial(n - 1) you are saying: "I will handle the multiplication
by n; you (recursive call) handle the rest." The call stack keeps track of all
the pending multiplications until the base case provides the first concrete value
to hand back up the chain.
Where to go next
Next: recursion in Python — implementing factorial and Fibonacci with print traces so you can watch the call sequence unfold, and a note on Python's built-in recursion limit.
Lab: algorithm practice
Three guided problems — most-common word, pair sums, and anagram check — each asking you to pick the right data structure and apply the patterns you have learned.
Recursion in Python
Implement factorial and Fibonacci recursively, add print traces to see the call sequence, and learn about Python's recursion limit.