← Back to course
Code Crew G5 / Week 04 / Wednesday
3/6
Week 04 · Base case

Wednesday

Answers come back up
// Knowing when to stop
⏱ about 15 min

Wednesday: Answers come back up

The fleet stacks fuel cells in a triangle. The top row has 1 cell, the next has 2, then 3, then 4.

"How many cells is that?" Rocket asks. "I could count them one by one."

Raven remembers the crew tunnel. "What do you notice if you take away the bottom row of 4?"

"A smaller triangle is left!" says Rocket. "So the total is 4 plus the smaller triangle."

Nova sparkles. "Here is a hint. Let the answers travel back up, like in the tunnel."

A recursion that returns

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(4))
Output:
10
  • Base case: sum_to(0) returns 0. A triangle with no rows has no cells.
  • Smaller step: sum_to(n) returns n plus sum_to(n - 1).

Questions go down: sum_to(4) asks sum_to(3), which asks sum_to(2), and so on to sum_to(0). Answers come back up.

CallWaits forReturns
sum_to(0)nothing (base case)0
sum_to(1)sum_to(0)1 + 0 = 1
sum_to(2)sum_to(1)2 + 1 = 3
sum_to(3)sum_to(2)3 + 3 = 6
sum_to(4)sum_to(3)4 + 6 = 10
TAP THE RETURN VALUES INTO THE ORDER THEY COME BACK.
  • Tap a card.
  • Then tap its spot.
11st
22nd
33rd
44th
55th
What does print(sum_to(5)) show?
WHY THIS EXERCISEsum_to(5) is 5 plus the answer for the smaller triangle, sum_to(4).
THINK ABOUT SUM_TO.
  • Read the question.
  • Tap your answer.
Which call returns first?
What would sum_to(0) return if the base case said return 1?

Practice lab: stacking crates

def stack(n):
    if n == 0:
        return 0
    return 2 + stack(n - 1)

print(stack(3))
print(stack(5))
What does stack(0) return?
What does stack(1) return?
What does print(stack(3)) show?
What does print(stack(5)) show?
RETURN CHECK
  • Read the question.
  • Tap your answer.
Which call to stack returns first?
Suppose the base case returned 5. What would stack(3) return?
What does stack(4) return?
StatementTrue or false?
stack(2) waits for stack(1).?
stack(2) returns 2.?
The answer for stack(3) is built on the way back up.?
sum_to(3) returns 6.?
WHY THIS EXERCISEReturn values climb back up the stack, one call at a time.
What does print(sum_to(6)) show?
WHY THIS EXERCISEsum_to(6) is 6 plus the answer for sum_to(5).

Superb! Return values climb back up the stack, one call at a time. Tomorrow we use this to add up a whole list.

← Tuesday