Imagine counting down from 3. You say 3, then 2, then 1—and stop. A recursive countdown needs that same stopping instruction. If it keeps calling itself with a smaller number but never returns, it continues past zero. section 3.2
That stopping instruction is the base case: the situation a recursive function handles without calling itself again. The recursive case handles everything else by calling the function on a smaller problem. For a countdown, print the current number; if it is 1 or less, return. Otherwise, count down from the number before it. 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
The countdown code puts the return and the recursive call in separate branches. Try tracing it with 3: which branch runs when the input reaches 1? section 3.2
How do you choose a base case for a less familiar problem? Look for the simplest version you can solve immediately, then make each recursive call reduce the problem toward it. To divide a rectangular plot into the largest possible square plots, the easy case is a rectangle whose one side is a multiple of the other. Otherwise, solve the smaller leftover rectangle. section 4.1
An array that needs no sorting
Quicksort can return an empty array or a one-element array unchanged: either is already sorted. For a larger array, it partitions around a pivot, recursively sorts the smaller sub-arrays, and combines them. Those sub-arrays eventually reach the base case. section 4.2
def quicksort(array):
if len(array) < 2:
return array #1
else:
pivot = array[0] #2
less = [i for i in array[1:] if i <= pivot] #3
greater = [i for i in array[1:] if i > pivot] #4
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
#1 Base case: arrays with 0 or 1 element are already sorted.
#2 Recursive case
#3 Sub-array of all the elements less than the pivot
#4 Sub-array of all the elements greater than the pivot
See how `len(array) < 2` returns immediately, while the other branch makes two recursive calls. section 4.2
