← Back to course
Code Crew G5 / Week 04 / Thursday
4/6
Week 04 · Base case

Thursday

Sum of a list
// Knowing when to stop
⏱ about 15 min

Thursday: Sum of a list

Nova has a list of glow readings from three stars. Rocket wants the total, and he wants to use recursion.

"But a list is not a number," he says. "How do I make a list smaller?"

Raven covers the first number with her finger. "What do you notice about what is left?"

"It is a shorter list!" Rocket says.

Nova hums. "Here is a hint. The total is the first number plus the total of the rest."

Slicing off the first item

A slice takes part of a list. nums[1:] means every item from spot 1 to the end. It skips the first item.

nums = [3, 5, 2]
print(nums[0])
print(nums[1:])
print(nums[1:][1:])
print([2][1:])
Output:
3
[5, 2]
[2]
[]

A list with one item, sliced, becomes the empty list []. The empty list is our base case. It adds up to 0.

The total function

def total(nums):
    if nums == []:
        return 0
    return nums[0] + total(nums[1:])

print(total([3, 5, 2]))
Output:
10
  1. total([3, 5, 2]) waits for total([5, 2]).
  2. total([5, 2]) waits for total([2]).
  3. total([2]) waits for total([]).
  4. total([]) is the base case. It returns 0.
  5. Answers come back: 2 plus 0 is 2. Then 5 plus 2 is 7. Then 3 plus 7 is 10.
What does total([2]) return?
What does total([5, 2]) return?
What does print(total([4, 4, 1, 6])) show?
WHY THIS EXERCISEThe answer matches a loop total, because both add each item exactly once.
BASE CASE CHECK.
  • Read the question.
  • Tap your answer.
What is the base case of total?
How many calls does total([3, 5, 2]) make in all, counting the first?

Practice lab: count the items

def count_items(nums):
    if nums == []:
        return 0
    return 1 + count_items(nums[1:])

print(count_items([4, 9, 2]))
print([7, 8, 9][1:])
What does count_items([5, 5, 5, 5]) return?
What does count_items([]) return?
What does print([7, 8, 9][1:]) show?
What does total([1, 2, 3]) return?
COUNT OR TOTAL?
  • Read the question.
  • Tap your answer.
What does count_items work out?
What is the base case of count_items?
How many calls does count_items([4, 9, 2]) make, counting the first?
StatementTrue or false?
nums[1:] is always one item shorter than nums, if nums is not empty.?
count_items([9]) returns 9.?
total([9]) returns 9.?
Both functions stop at the empty list.?
WHY THIS EXERCISEThe same shape works for many jobs. Only the step changes.
What does print(total([10, 20, 5])) show?
WHY THIS EXERCISEtotal adds each item once on the way back up.

Brilliant! You added a list with recursion. Tomorrow we count with recursion and fix a sneaky base case bug.

← Wednesday