黑马程序员技术交流社区

标题: 递归例一 [打印本页]

作者: bcair 时间: 2018-10-9 00:42
标题: 递归例一

函数递归案例一

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

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

1计算一个嵌套的子列表结构中多个数字的总和2[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)后结束，上层函数重新接替程序的执行权继续未完成的遍历求和。控制权的变化如下面的示意图。

  To illustrate how the place of program control variables:
  -* =down= to deeper depth
  -& =up= to lower depth
  - =hold= current level

  each ___ represents one list elements in current list

  | 0 |  1 |  2 | 3 |  4 |  5 |  6 | 7 |  8 |
  |---+----+----+---+----+----+----+---+----|
  | 1 | -* | | | | | -* | | | [1, _____________ , 6, ______ ]
  | 2 | | -* | | | -& | | - | -& |       [2, ______, 5], [7, 8]
  | 3 | | | - | -& | | | | |          [3, 4]

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

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

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

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2