A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

严家华

初级黑马

  • 黑马币:13

  • 帖子:6

  • 精华:0

© 严家华 初级黑马   /  2019-3-27 20:09  /  1235 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

计算一个嵌套的子列表结构中多个数字的总和
[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,$ 计算正确。

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马