← Back to course
Code Crew G5 / Week 04 / Monday
1/6
Week 04 · Base case

Monday

Two parts of every recursion
// Knowing when to stop
⏱ about 15 min

Monday: Two parts of every recursion

Rocket is writing a beeper for the docking bay. It should beep a few times, then say done.

"I think recursion fits," he says. "But what makes recursion actually work?"

Raven lays last week's countdown next to the staircase. "What do you notice that they both have?"

Rocket points. "They both stop when n is 0. And they both call themselves with n minus 1."

Nova shines a light on each part. "Here is a hint. Give those two parts names, and look for them every time."

Base case and smaller step

Every working recursion has two parts. The base case is the stop. It does not call the function again.

The smaller step calls the function again on a smaller problem. Each call must get closer to the base case.

def beep(n):
    if n == 0:
        print("done")
    else:
        print("beep")
        beep(n - 1)

beep(3)
Output:
beep
beep
beep
done
PartLines in beepJob
Base caseif n == 0: print("done")Stops the calls
Smaller stepbeep(n - 1)Calls again with a smaller n
FIND THE TWO PARTS.
  • Read the question.
  • Tap your answer.
In countdown, which part prints Liftoff!?
In stairs, which line is the smaller step?
How many times does beep(5) print the word beep?
WHY THIS EXERCISEThe smaller step runs for each number from 5 down to 1. Then the base case prints done.
StatementTrue or false?
The base case calls the function again.?
The smaller step should move closer to the base case.?
beep(0) prints only done.?
WHY THIS EXERCISEIf the base case called again, nothing would ever stop the recursion.

Practice lab: find the parts

def tick(n):
    if n == 0:
        print("ring")
    else:
        print("tick", n)
        tick(n - 1)

tick(2)
What word does the base case print?
How many lines does tick(4) print?
What goes inside the brackets of the smaller step call?
What is the only line tick(0) prints?
PART CHECK
  • Read the question.
  • Tap your answer.
Which part of tick prints tick 2?
Which call reaches the base case for tick(2)?
Why must each call use a smaller n?
StatementTrue or false?
tick has a base case.?
tick(3) prints ring before tick 3.?
The base case in tick does not call tick again.?
tick(1) prints two lines.?
WHY THIS EXERCISEThe smaller step runs once per number, then the base case finishes.
How many times does tick(6) print a line that starts with tick?
WHY THIS EXERCISEThe smaller step runs 6 times. Then the base case prints ring.

Great job naming the parts! Tomorrow we find out what happens when one part goes missing.