4.3. 计算一个数列的和

4.3. Calculating the Sum of a List of Numbers

中文英文

我们将从一个简单的问题开始，这个问题你已经知道如何解决，而无需使用递归。假设你想计算一个数字列表的总和，比如：[1, 3, 5, 7, 9]。一个计算总和的迭代函数如 ActiveCode 4.3.1 所示。这个函数使用一个累加器变量（the_sum）来计算列表中所有数字的运行总和，开始时为0，然后将列表中的每个数字相加。

def list_sum(num_list):
    the_sum = 0
    for i in num_list:
        the_sum = the_sum + i
    return the_sum

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

假设你没有 while 循环或 for 循环。你将如何计算一个数字列表的总和？如果你是一个数学家，你可能会从加法是一个为两个参数定义的函数（即一对数字）开始。为了将问题从加法列表重新定义为加法对数字，我们可以将列表重新写成一个完全括起来的表达式。这样的表达式看起来像这样：

\(((((1 + 3) + 5) + 7) + 9)\)

我们也可以将表达式以另一种方式括起来，

\((1 + (3 + (5 + (7 + 9))))\)

注意到最内层的括号 \((7 + 9)\) 是一个可以在没有循环或任何特殊结构的情况下解决的问题。事实上，我们可以使用以下简化序列来计算最终的总和。

\(\begin{align} total &= \ (1 + (3 + (5 + (7 + 9)))) \\ total &= \ (1 + (3 + (5 + 16))) \\ total &= \ (1 + (3 + 21)) \\ total &= \ (1 + 24) \\ total &= \ 25 \end{align}\)

我们如何将这个想法转化为Python程序？首先，让我们用Python列表的术语重新表述总和问题。我们可以说，列表 num_list 的总和是列表第一个元素（num_list[0]）和列表其余部分的总和（num_list[1:]）。用函数形式表述为：

\(list\_sum(num\_list) = first(num\_list) + list\_sum(rest(num\_list))\)

在这个方程中，first(num_list) 返回列表的第一个元素，rest(num_list) 返回除第一个元素外的列表。这在Python中可以很容易地表示，如 ActiveCode 4.3.2 所示。

def list_sum(num_list):
    if len(num_list) == 1:
        return num_list[0]
    else:
        return num_list[0] + list_sum(num_list[1:])

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

在这个列表中，有几个关键点需要注意。首先，在第2行，我们检查列表的长度是否为1。这个检查至关重要，是我们从函数中逃逸的条件。长度为1的列表的总和很简单；它只是列表中的那个数字。其次，在第5行，我们的函数调用了自己！这就是我们称 list_sum 算法为递归的原因。递归函数是调用自身的函数。

Figure 4.1 显示了计算列表 [1, 3, 5, 7, 9] 所需的一系列 递归调用。你应该把这一系列调用看作是一系列简化。每次我们进行递归调用时，我们在解决一个更小的问题，直到我们达到问题不能再变得更小的点。

Figure 4.1: 递归调用序列，计算数字列表的和

当我们到达问题变得尽可能简单的点时，我们开始将每个小问题的解决方案拼凑在一起，直到最初的问题得到解决。Figure 4.2 显示了在 list_sum 函数通过调用序列向后工作时执行的加法。当 list_sum 从最上层的问题返回时，我们得到了整个问题的解决方案。

Figure 4.2: 递归返回序列，计算数字列表的和

We will begin our investigation with a simple problem that you already know how to solve without using recursion. Suppose that you want to calculate the sum of a list of numbers such as: \([1, 3, 5, 7, 9]\). An iterative function that computes the sum is shown in ActiveCode 4.3.1. The function uses an accumulator variable (the_sum) to compute a running total of all the numbers in the list by starting with \(0\) and adding each number in the list.

def list_sum(num_list):
    the_sum = 0
    for i in num_list:
        the_sum = the_sum + i
    return the_sum

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

Pretend for a minute that you do not have while loops or for loops. How would you compute the sum of a list of numbers? If you were a mathematician you might start by recalling that addition is a function that is defined for two parameters, a pair of numbers. To redefine the problem from adding a list to adding pairs of numbers, we could rewrite the list as a fully parenthesized expression. Such an expression looks like this:

\(((((1 + 3) + 5) + 7) + 9)\)

We can also parenthesize the expression the other way around,

\((1 + (3 + (5 + (7 + 9))))\)

Notice that the innermost set of parentheses, \((7 + 9)\), is a problem that we can solve without a loop or any special constructs. In fact, we can use the following sequence of simplifications to compute a final sum.

\(\begin{align} total &= \ (1 + (3 + (5 + (7 + 9)))) \\ total &= \ (1 + (3 + (5 + 16))) \\ total &= \ (1 + (3 + 21)) \\ total &= \ (1 + 24) \\ total &= \ 25 \end{align}\)

How can we take this idea and turn it into a Python program? First, let’s restate the sum problem in terms of Python lists. We might say the sum of the list num_list is the sum of the first element of the list (num_list[0]) and the sum of the numbers in the rest of the list (num_list[1:]). To state it in a functional form:

\(list\_sum(num\_list) = first(num\_list) + list\_sum(rest(num\_list))\)

In this equation \(irst(num\_list)\) returns the first element of the list and \(rest(num\_list)\) returns a list of everything but the first element. This is easily expressed in Python as shown in ActiveCode 4.3.2.

    def list_sum(num_list):
        if len(num_list) == 1:
            return num_list[0]
        else:
            return num_list[0] + list_sum(num_list[1:])

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

There are a few key ideas in this listing to look at. First, on line 2 we are checking to see if the list is one element long. This check is crucial and is our escape clause from the function. The sum of a list of length 1 is trivial; it is just the number in the list. Second, on line 5 our function calls itself! This is the reason that we call the list_sum algorithm recursive. A recursive function is a function that calls itself.

Figure 4.1 shows the series of recursive calls that are needed to sum the list \([1, 3, 5, 7, 9]\). You should think of this series of calls as a series of simplifications. Each time we make a recursive call we are solving a smaller problem, until we reach the point where the problem cannot get any smaller.

Figure 4.1: Series of Recursive Calls Adding a List of Numbers

When we reach the point where the problem is as simple as it can get, we begin to piece together the solutions of each of the small problems until the initial problem is solved. Figure 4.2 shows the additions that are performed as list_sum works its way backward through the series of calls. When list_sum returns from the topmost problem, we have the solution to the whole problem.

Figure 4.2: Series of Recursive Returns from Adding a List of Numbers

---

最后更新: 2024年9月12日
创建日期: 2024年9月9日