Writing a Recursive Python Function to Process a List

Hello! Last lesson, you traced recursive calls down to a base case and followed their return values back up. Now you’ll use that same method to write a function that processes a list. We’ll start with a familiar task—adding numbers—then reuse the pattern for a different task. Allow about 30–35 minutes, including time to run the code.

Turn a list into a smaller list

Suppose you want the sum of [1, 3, 5, 7, 9]. A loop can keep a running total, but recursion asks a different question: What part can this call handle, and what smaller version of the same problem can it hand to another call?

The first call can handle 1 and ask for the sum of [3, 5, 7, 9]. That call can handle 3 and ask for the sum of [5, 7, 9]. In Python, numbers[0] gets the first element, while numbers[1:] makes a list containing the rest.

Read the explanation in Runestone Academy’s Calculating the Sum of a List of Numbers. It develops this first-element-and-rest idea before showing the recursive calls and returns.

The reading uses a one-element list as its base case. That works for nonempty input. For a function you can also call with [], a more useful base case is: the sum of an empty list is 0. Every nonempty call removes one element, so it will eventually reach that case.

Write the recursive sum

Here is the complete function. Type it out and run it; the two branches are the whole pattern.

def list_sum(numbers):
    if numbers == []:
        return 0

    first = numbers[0]
    rest = numbers[1:]
    return first + list_sum(rest)


print(list_sum([1, 3, 5, 7, 9]))  # 25

The base case returns an answer without calling list_sum again. In the recursive step, rest is shorter than numbers, and the current call waits for list_sum(rest) before it can add first. The return is essential: it sends the completed sum back to the call that was waiting.

This function assumes a list of numbers that can be added together. Check its boundaries, not just the five-element example:

assert list_sum([]) == 0
assert list_sum([8]) == 8
assert list_sum([4, -6, 2]) == 0

For [8], the function adds 8 to the sum of [], which is 0. That is why no separate one-element case is needed. The function also leaves the input list unchanged: slicing creates a new list for each recursive call.

Follow the answers back

The diagram below shows the return path for the same five numbers. It uses the reading’s one-element base case, so its final call returns 9 rather than making one more call with []. Both versions produce the same additions on the way back.

For our empty-list version, the deepest call returns 0. The call holding 9 can then return 9 + 0; the call holding 7 returns 7 + 9; and the earlier calls finish in reverse order. As in the factorial trace from last lesson, reaching the base case is only the midpoint: the waiting calls still have work to do.

A compact way to check whether your function is sound is to ask:

1. What does it return for the smallest valid input?
2. Does every other call receive a smaller list?
3. If the smaller call gives the right answer, does the current call combine it into the right answer?

For list_sum, those answers are 0 for [], one fewer element on each call, and “add back the element this call handled.”

Reuse the pattern for another list task

Recursion does not require addition of the list’s values. Suppose you want to count how many numbers are positive. The sum of an empty list becomes a count of zero for an empty list. For a nonempty list, the current call contributes either 1 or 0, then asks for the count in the rest.

def count_positive(numbers):
    if numbers == []:
        return 0

    first = numbers[0]
    rest = numbers[1:]

    if first > 0:
        contribution = 1
    else:
        contribution = 0

    return contribution + count_positive(rest)


assert count_positive([]) == 0
assert count_positive([-2, 5, 0, 7]) == 2

Notice what stayed the same: the base case, the shorter-list call, and the need to return a combined result. What changed was what one element contributes. This is a reusable way to design recursive list functions: decide the empty-list answer, decide what to do with one element, and trust the recursive call to process the rest.

For ordinary flat lists, a loop is often more practical in Python. Recursion keeps unfinished calls, and numbers[1:] creates a new list each time. For now, the goal is to write and reason about the function correctly; the next module will give you tools to compare its efficiency with a loop.

Key takeaways

To process a list recursively, handle an empty list directly, then combine the first element’s contribution with the result for the rest. Make sure every recursive call gets a shorter list and that you return the combined result. You can use the same structure for sums, counts, and other list-wide results.

Next, you’ll begin measuring how an algorithm’s work grows as its input gets larger.