LESSON 349 OF 634 · RECURSION

Sum of a List, Recursively in C++

Practice O(n)

You get a vector nums of whole numbers. Return the sum of all its numbers.

Solve it with recursion, a function that calls itself. A loop would work too, but this lesson is about the recursive call.

The sum of an empty vector is 0.

Example 1:

Input: nums = [3,8,-5,10,2]
Output: 18
Explanation: 3 + 8 - 5 + 10 + 2 = 18.

Example 2:

Input: nums = [-6]
Output: -6
Explanation: With one number, the sum is that number.

Example 3:

Input: nums = []
Output: 0
Explanation: There are no numbers to add.

Constraints:

0 to 1,000 numbers.
Each number is from -10,000 to 10,000.

Note:

Your solution should run in O(n) time, where n is the length of nums.

The sum of the whole vector is its first number plus the sum of the numbers after it. That second sum is the same problem, with one number fewer.

Give the recursive function an index i, where its part of the vector starts. Each call moves i one step to the right. When i is past the last number, nothing is left, so return 0.

There are n + 1 calls, and each one does a fixed amount of work: O(n) time.
Each call waits for the next one, so up to n + 1 calls sit on the call stack at once: O(n) extra space. That is also why nums holds at most 1,000 numbers here.
Passing a copy of the rest of the vector to each call, instead of an index, would cost O(n²) time.

STEP 1 OF 4

Guided

Ctrl + Enter to check

Sum of a List, Recursively in C++

Recursive List Sum in C++