The first value and the rest
Add up a list by taking the first value and trusting a smaller call to add up the rest. About 10 minutes.
One value, then the rest
To add up 4, 7, 2, 9, you could say: the total is 4 plus the total of 7, 2, 9. And that smaller total is 7 plus the total of 2, 9. Each step peels off one value and leaves a shorter list.
Instead of making shorter lists, pass the position you're up to. The call for position i adds the value at i to the answer for position i + 1. When you go past the last position, nothing is left, so the answer is 0.
def sum_list(nums):
def go(i):
if i == len(nums):
return 0
return nums[i] + go(i + 1)
return go(0)Position 0: keep 4, ask for the total from position 1.
What should the call return when the position is past the last value?
- A0, because there is nothing left to add
- BThe last value
- C1
Show the answer
0, because there is nothing left to add. Zero is the total of an empty list, and adding it changes nothing.
Add up the list
nums is a list of whole numbers. Return the sum of all its values, using a recursive function that handles one position and calls itself for the next.
nums = [4, 7, 2, 9] → 22
0 ≤ length ≤ 500 · −1,000 ≤ value ≤ 1,000