← Back to course
Code Crew G5 / Week 05 / Thursday
4/6
Week 05 · Loop or recursion?

Thursday

Recursion into a loop
// The same job, two ways
⏱ about 15 min

Thursday: Recursion into a loop

The fleet sends signals home through relay stations. Each station doubles the signal power.

Nova wrote a recursive function called boost. Rocket wants a loop version for the relay panel.

"A signal of 3 through 4 stations," Rocket says. "That is 3, then 6, then 12, then 24, then 48!"

Raven asks, "What do you notice about each station?"

"Every station does the same thing. It doubles," Rocket says. Nova hums. "Here is a hint. Same thing, many times. Sound familiar?"

The recursive version

def boost(power, stations):
    if stations == 0:
        return power
    return boost(power * 2, stations - 1)

print(boost(3, 4))
Output:
48

Each call doubles the power and has one fewer station left. With no stations left, the power is returned as it is.

The loop version

range(stations) makes the numbers 0 up to one less than stations. So the loop runs exactly stations times.

def boost_loop(power, stations):
    for i in range(stations):
        power = power * ____
    return power

print(boost_loop(3, 4))
What number goes in the blank so boost_loop(3, 4) returns 48?
WHY THIS EXERCISEThe loop body does the work of one station. Doubling means times 2.
What does boost(5, 3) return?
What does boost(7, 0) return?
StatementTrue or false?
The base case stations == 0 matches the loop running out of turns.?
boost_loop calls boost_loop.?
boost(3, 4) and boost_loop(3, 4) return the same number.?
WHY THIS EXERCISEConverting keeps what the program does. Only the shape of the code changes.

Practice lab: triple it

def triple(n, times):
    if times == 0:
        return n
    return triple(n * 3, times - 1)

def triple_loop(n, times):
    for i in range(times):
        n = n * 3
    return n

print(triple(2, 3), triple_loop(2, 3))
What does triple(1, 2) return?
What does triple(5, 0) return?
What does the print line show for triple_loop(2, 3)?
How many times does the loop body run for triple_loop(4, 5)?
MATCH THE PARTS
  • Read the question.
  • Tap your answer.
The base case times == 0 matches what in the loop?
What numbers does range(3) make?
What does triple(1, 3) return?
StatementTrue or false?
triple and triple_loop always return the same number.?
triple_loop calls itself.?
times - 1 is the smaller step in triple.?
triple(2, 1) returns 5.?
WHY THIS EXERCISEThe two versions do the same work in a different shape.
What does triple(10, 2) return?
WHY THIS EXERCISETwo triplings: 10 times 3 times 3.

Excellent! You can now move between loops and recursion in both directions. Tomorrow we decide which one to pick.

← Wednesday