← Back to course
Code Crew G5 / Week 04 / Friday
5/6
Week 04 · Base case

Friday

Count and debug
// Knowing when to stop
⏱ about 15 min

Friday: Count and debug

Rocket copies the total function to add a new list. The answer comes out 11, but the numbers only add to 10.

"I checked my adding three times," Rocket says. "I am sure the list is right."

Raven traces the calls on paper. "What do you notice about the very last call?"

Rocket squints. "The empty list returns 1. But an empty list has nothing in it!"

Nova cheers. "Great discovery! Here is a hint. Every wrong base case answer gets added in."

A buggy base case

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

print(total([3, 5, 2]))
Output:
11

The base case is reached once, at the very end. Its value is added into every answer above it. So a base case of 1 makes every total 1 too big.

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

print(total([3, 5, 2]))
What should the base case return?
WHY THIS EXERCISEThe empty list adds nothing, so its total must be 0.

Counting with recursion

This function counts the readings bigger than 5. It has one base case and two smaller steps.

def count_big(nums):
    if nums == []:
        return 0
    if nums[0] > 5:
        return 1 + count_big(nums[1:])
    return count_big(nums[1:])

print(count_big([8, 2, 9, 6, 1]))
Output:
3
  • If the first item is bigger than 5, count 1 and add the count of the rest.
  • If not, the answer is just the count of the rest.
USE COUNT_BIG.
  • Read the question.
  • Tap your answer.
What does count_big([7, 7, 3]) return?
What does count_big([]) return?
Statement about count_bigTrue or false?
Every call makes the list one item shorter.?
count_big([6]) returns 1.?
The base case returns 1.?
WHY THIS EXERCISEBoth smaller steps use nums[1:], so every path moves toward the empty list.

Practice lab: count the small ones

def count_small(nums):
    if nums == []:
        return 0
    if nums[0] < 3:
        return 1 + count_small(nums[1:])
    return count_small(nums[1:])

print(count_small([1, 5, 2, 2, 8]))
What does count_small([4, 1]) return?
What does count_small([2, 2, 2]) return?
What does count_small([9]) return?
Suppose the base case returned 1. What would the program show?
DEBUG CHECK
  • Read the question.
  • Tap your answer.
What does count_small([]) return?
Suppose the last line said count_small(nums) without the slice. What happens?
To count numbers bigger than 5, what would you change?
StatementTrue or false?
count_small has one base case.?
count_small has two smaller steps.?
count_small([3]) returns 1.?
Both smaller steps use nums[1:].?
WHY THIS EXERCISEEvery path moves toward the empty list, so the recursion always stops.

Week 4 complete! You can name the base case, spot a missing one and fix a wrong one. Next week we race loops against recursion.

← Thursday