LESSON 355 OF 640 · RECURSION

Sum of a List, Recursively in Swift

Practice O(n)

You get an array 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 array 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 array 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 array 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 array 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 Swift

Recursive List Sum in Swift