函数递归案例一

摘自 Python Learning Chap.19
中文译名《Python学习手册》

考虑下面这样的一个任务：

计算一个嵌套的子列表结构中多个数字的总和
[1, [2, [3, 4], 5], 6, [7, 8]]

为什么 & 如何 递归

很显然仅while循环并不能解决上面的问题，简单的循环语句中包含 4 个部分：

• 计数器

• 判断语句

• loop body

• 处理计数器，防止死循环

这里我们将对 [1, 4, 6, 3, 0] 这中无嵌套子列表的列表各个元素求和的普通循环语句块，称为简单求和循环，特点是列表元素个数已知且每个元素都为整型。

L = [1, 4, 6, 3, 0]
sum0 = 0
for _ in L:
    sum0 += _
print("total sum euqals to " + str(sum0))

若直接用上面的代码来计算 [1, [2, [3, 4], 5], 6, [7, 8]] 中个元素的和，需每次 for 遍历都判断当前元素的类型，碰到新的子列表元素时，添加一个简单求和循环块，返回到外层循环继续。

但如果我们事先无法得知列表的嵌套情况时，上面的思路会行不通，因为简单求和循环的个数不确定。

在《Python 学习手册》内作者定义了一个递归函数来计算列表所有元素的和：

def sumtree(L):
    tot = 0
    for x in L:
        if not isinstance(x, list):
            tot += x
        else:
            tot += sumtree(x)
    return tot

函数isinstance(x, list) 会判断 x 是否为一个列表实例。由于for语句的特殊性，这个例子中的递归调用不需要额外的代码来终止，分析如下

定义一个函数 sumtree（L)

– 实现的功能：求参数列表 L 内各元素的和

– 局部变量 tot 保存列表内所有元素的和的值

– 函数结束会返回 tot 值

功能实现上，对列表元素 x 遍历，进行判断

– 为整型，该元素为求和的增量值： tot += x

– 为列表，将它作为参数重新调用函数 sumtree(x)，让新的函数去求子列表中各元素的和

函数 sumtree(L) 只求元素为纯数字的列表的和，如果元素 x 为嵌套的列表时，本次就和暂停，将它“踢给”下层的函数 sumtree(x) 来处理，下层调用函数获得程序的执行权，在求出所有元素的和并返回给上层函数 sumtree(L)后结束，上层函数重新接替程序的执行权继续未完成的遍历求和。

最后定义列表并调用函数，求出列表内所有数字的和

L = [1, [2, [3, 4], 5], 6, [7, 8]]
print(sumtree(L))       # RESULT： 36

得到36，由等差数列求和公式知前 8 个数的和为 $\frac{8 \cdot (1 + 8)}{2} = 36,$ 计算正确。

函数递归案例一

摘自 Python Learning Chap.19
中文译名《Python学习手册》

考虑下面这样的一个任务：

计算一个嵌套的子列表结构中多个数字的总和
[1, [2, [3, 4], 5], 6, [7, 8]]

为什么 & 如何 递归

很显然仅while循环并不能解决上面的问题，简单的循环语句中包含 4 个部分：

• 计数器

• 判断语句

• loop body

• 处理计数器，防止死循环

这里我们将对 [1, 4, 6, 3, 0] 这中无嵌套子列表的列表各个元素求和的普通循环语句块，称为简单求和循环，特点是列表元素个数已知且每个元素都为整型。

L = [1, 4, 6, 3, 0]
sum0 = 0
for _ in L:
    sum0 += _
print("total sum euqals to " + str(sum0))

若直接用上面的代码来计算 [1, [2, [3, 4], 5], 6, [7, 8]] 中个元素的和，需每次 for 遍历都判断当前元素的类型，碰到新的子列表元素时，添加一个简单求和循环块，返回到外层循环继续。

但如果我们事先无法得知列表的嵌套情况时，上面的思路会行不通，因为简单求和循环的个数不确定。

在《Python 学习手册》内作者定义了一个递归函数来计算列表所有元素的和：

def sumtree(L):
    tot = 0
    for x in L:
        if not isinstance(x, list):
            tot += x
        else:
            tot += sumtree(x)
    return tot

函数isinstance(x, list) 会判断 x 是否为一个列表实例。由于for语句的特殊性，这个例子中的递归调用不需要额外的代码来终止，分析如下

定义一个函数 sumtree（L)

– 实现的功能：求参数列表 L 内各元素的和

– 局部变量 tot 保存列表内所有元素的和的值

– 函数结束会返回 tot 值

功能实现上，对列表元素 x 遍历，进行判断

– 为整型，该元素为求和的增量值： tot += x

– 为列表，将它作为参数重新调用函数 sumtree(x)，让新的函数去求子列表中各元素的和

函数 sumtree(L) 只求元素为纯数字的列表的和，如果元素 x 为嵌套的列表时，本次就和暂停，将它“踢给”下层的函数 sumtree(x) 来处理，下层调用函数获得程序的执行权，在求出所有元素的和并返回给上层函数 sumtree(L)后结束，上层函数重新接替程序的执行权继续未完成的遍历求和。

最后定义列表并调用函数，求出列表内所有数字的和

L = [1, [2, [3, 4], 5], 6, [7, 8]]
print(sumtree(L))       # RESULT： 36

得到36，由等差数列求和公式知前 8 个数的和为 $\frac{8 \cdot (1 + 8)}{2} = 36,$ 计算正确。