Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. Every recursive function has exactly two parts:
- Base case — the smallest input you can answer directly, with no further call. This stops the recursion.
- Recursive case — reduce the problem one step and call yourself, then combine.
The counting-down example makes the skeleton concrete:
def countdown(n):
if n == 0: # base case: nothing left to do
return
print(n) # do this step's work
countdown(n - 1) # recurse on a smaller n
The base case is not optional. Forget it (or never move toward it) and the function calls itself forever until the program crashes with a stack overflow. So the two questions to ask for any recursive problem are: what is the smallest case I can answer outright, and how do I take one step toward it? Answer those and the code almost writes itself.