Functions that call themselves (recursion)

Your phone wants to know how many photos are in a folder. But the folder holds other folders, and some of those hold more folders.

You cannot know how deep it goes. There is a neat answer: count the photos here, then ask the same question of each folder inside.

A recursive function has two parts. The base case is small enough to answer at once, with no more calls.

The recursive case calls the same function on a smaller problem. Each call must move closer to the base case. A countdown from 3 calls itself with 2, then 1, then 0, and 0 is the base case.

# A countdown that calls itself.
def countdown(n):
    if n == 0:
        print("Go!")
        return
    print(n)
    countdown(n - 1)

countdown(3)
# Change the 3 to 5. Then change n == 0 to n == 2.
# What does the second change do?

When a function calls itself, the first call has not finished. It waits on the call stack, the same stack as in the last lesson.

Each new call is pushed on top. When the base case returns, the calls are popped one at a time, last in first out. Each one finishes its own work with the answer it was given.

# Watch the call stack grow and shrink.
def factorial(n, depth):
    gap = "    " * depth
    print(gap + "call factorial(" + str(n) + ")")
    if n == 1:
        answer = 1
    else:
        answer = n * factorial(n - 1, depth + 1)
    print(gap + "factorial(" + str(n) + ") returns " + str(answer))
    return answer

factorial(4, 0)
# Change 4 to 6. How deep does the stack go now?

Python allows about a thousand calls on the stack. After that it stops the program with a RecursionError, its name for a stack overflow.

The Run below times a function called down that calls itself with no base case. It never gets as far as a time. Read the last line it prints.

docker exec jupyter python3 -m timeit -s "def down(n):" -s "    return down(n - 1)" "down(5)"

A Fibonacci number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8. The neat recursive version calls itself twice each time.

So fib(5) works out fib(3) twice and fib(2) three times. The Runs time fib(20) and fib(25). Compare the two times, then count the calls in your notebook.

docker exec jupyter python3 -m timeit -s "def fib(n):" -s "    return n if n < 2 else fib(n - 1) + fib(n - 2)" "fib(20)"

docker exec jupyter python3 -m timeit -s "def fib(n):" -s "    return n if n < 2 else fib(n - 1) + fib(n - 2)" "fib(25)"

calls = 0

def fib(n):
    global calls
    calls = calls + 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

for n in [10, 15, 20, 25]:
    calls = 0
    print("fib(" + str(n) + ") =", fib(n), "after", calls, "calls")

Merge sort is recursive at heart. A list of 0 or 1 items is the base case. Otherwise, split it in half, merge sort each half, and merge the two answers.

Write it in your notebook using your merge from lesson 2. Check it against sorted on 1,000 random numbers.