Data structures and algorithms · Recursion

Recursion

A function that calls itself on a smaller problem. · 10 minutes

A recursive function solves a problem by calling itself on a smaller version of it, until the problem is so small the answer is obvious — the base case. Each call gets its own frame with its own names, stacked on top of the caller.

Predict first

When countdown(3) prints 3, how many calls to countdown are open (started but not finished)?

1def countdown(n):
2    if n == 0:
3        print("go")
4        return
5    countdown(n - 1)
6    print(n)
7 
8countdown(3)