Imagine searching for a key in a box full of smaller boxes. You could keep a pile of boxes to check. Or, whenever you find another box, you could search it in the same way. That second approach is recursion: a function calls itself. It can make a solution clearer, though it does not make it faster by itself. section 3.1
A recursive function needs two parts:
- A base case stops the calls. Without one, even a simple countdown can keep going past zero. section 3.2
- A recursive case calls the function again. For a countdown, it passes a number one smaller than before. section 3.2
def countdown(i):
print(i)
if i <= 1: #1
return
else: #2
countdown(i-1)
countdown(3)
#1 Base case
#2 Recursive case
Run this countdown with 3, then trace the calls with pen and paper. Where does it stop calling itself? section 3.2 section 3.0
What happens while one call waits for another? The call stack keeps track. In a factorial calculation such as 5 × 4 × 3 × 2 × 1, each call has its own value and waits for the smaller calculation to return. In the box search, the stack likewise remembers half-finished searches, replacing the explicit pile of boxes. section 3.5
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)
Follow the factorial calls down to 1, then follow their return values back up the stack. section 3.5
Recursion also supports divide and conquer: choose the simplest case, then reduce the problem until you reach it. To find the largest square that tiles a rectangular plot, you can apply the same task to a smaller leftover plot. The important question is: does each call bring you closer to the base case? section 4.1
Choose recursion when self-calls clarify the steps, not for an automatic speed gain. Every pending call uses stack memory; a very deep recursion can use a lot. A loop may be preferable when that cost matters. section 3.1 section 3.5
