← Back to course
Python 11-12 / Week 10 / Monday
1/6
Week 10 · Recursion

Monday

A function that calls itself
// A base case, a smaller call, and a stack of calls to trace
⏱ about 30 min

Monday: A Function That Calls Itself

Comet bursts into the maker space with her sketch notebook open. "New idea for the launch countdown," she says. "The function prints a number, then calls itself with one less."

Wren looks up from his clipboard. "A function that calls itself? What does the evidence say? When does it ever stop?"

"When it reaches zero," Comet says. "Then it prints Go! instead."

Nova hovers over the bench and projects a staircase of glowing cards, each one a little smaller. "How can I help?" she asks. "Each card is one call. Watch which card stops the climb."

Comet grins and turns to you. "Lead programmer, trace it before we run it."

Two parts every recursive function needs

A recursive function is a function that calls itself.

It needs at least one base case, which stops the recursion. It also needs at least one recursive call.

Recursion is another way to repeat, like a loop. Each call works on a smaller problem until the base case is reached.

# countdown.py
def countdown(n):
    if n == 0:
        print("Go!")
    else:
        print(n)
        countdown(n - 1)


countdown(3)
FIND THE PARTS
  • Read the question.
  • Tap your answer.
Which line holds the base case test?
Which line is the recursive call?
Why does the recursion stop?

Predict the output of countdown(3) before you look. Then compare with the run:

3
2
1
Go!
COUNT THE CALLS
  • Read the question.
  • Tap your answer.
Each call prints one line. How many calls does countdown(3) make in all?
What would countdown(5) print last?
At your computer
1. In IDLE, open a new file in your fieldsim folder and type countdown.py.
2. Save it and press F5 to run it. Check the four lines.
3. Change countdown(3) to countdown(5) and run it again.
4. Now misspell the recursive call as countdwn(n - 1). Run it and read the traceback calmly.
5. Fix the spelling and run it once more.

Here is what the misspelled call gives. The first call printed 3 before it reached the bad line:

# countdown.py (with a typo)
def countdown(n):
    if n == 0:
        print("Go!")
    else:
        print(n)
        countdwn(n - 1)


countdown(3)
3
Traceback (most recent call last):
  File "countdown.py", line 10, in <module>
    countdown(3)
    ~~~~~~~~~^^^
  File "countdown.py", line 7, in countdown
    countdwn(n - 1)
    ^^^^^^^^
NameError: name 'countdwn' is not defined. Did you mean: 'countdown'?
What is the name of this error?

Going down and coming back

A call does not finish until the call it made has finished. So work written after the recursive call happens on the way back.

Trace echo(3) on paper first. Write each line it prints, in order.

# echo.py
def echo(n):
    if n == 0:
        print("base case")
    else:
        print("going down", n)
        echo(n - 1)
        print("coming back", n)


echo(3)
going down 3
going down 2
going down 1
base case
coming back 1
coming back 2
coming back 3
PUT THE FIRST LINES OF ECHO(3) IN ORDER
  • ?going down 3
  • ?going down 1
  • ?coming back 1
  • ?base case
  • ?going down 2
WHY THIS EXERCISEThe calls go down to the base case first. Then each waiting call finishes, newest first.
StatementTrue or false?
A recursive function calls itself.?
A recursive function with no base case stops on its own.?
echo(1) prints coming back 1 before base case.?
Each recursive call should work on a smaller problem.?
WHY THIS EXERCISEThe base case stops the recursion, and each call must move toward it. Lines after the call run on the way back.

You traced your first recursive function, lead programmer. Tomorrow you will stack the calls up and watch the answers come back.