函数递归案例一

摘自 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,$ 计算正确。

函数递归案例一

摘自 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,$ 计算正确。