递归

sun-10387834 2019-03-29 原文

一：什么是递归？

　　递归是一种解决问题的方法，它把一个问题分解为越来越小的子问题，直到问题的规模小到
可以被很简单直接解决。通常为了达到分解问题的效果，递归过程中要引入一个调用自身的函数。
乍一看，递归算法并没有什么特别的地方，但是，利用递归我们能够写出极为简明的解决问题的方
法，而且如果不用递归，这些问题将具有很大的编程难度。

实例：计算列表中数字之和。

1 #方式一：遍历累加（普通人方式）
2 def list_sum(num_list):
3     the_sum = 0
4     for i in num_list:
5         the_sum += i
6     return the_sum
7 
8 print(list_sum([1, 3, 5, 7, 9]))

我们怎么样才能有一种神人一般的做法呢？首先让我们从 Python 列表的角度来重新叙述这个问题。由于数字列表的和是列表中的第一个元素（numList[0]）和剩下所有的元素（numList(1:)）之和的和，求和问题可以归纳成以下的式子：

1 listSum(numList)=first(numList)+listSum(rest(numList))

1 #方式二：递归求和（神人方式）
2 def list_sum(num_list):
3     if len(num_list) == 1:
4         return num_list[0]
5     else:
6         return num_list[0] + list_sum(num_list[1:])
7 
8 print(list_sum([1, 3, 5, 7, 9]))

方式二第3行代码是递归的结束条件，也就是能够解决问题的最小单元。在else中return num_list[0] + list_sum(num_list[1:])，其中num_list[0] 能够获取到列表的第一个值，list_sum(num_list[1:]) 这个参数则是再次调用求和函数计算除了列表第一个值之外的其他所有值的和（也就是方法自身调用自身），直到列表长度为1时，返回列表中第一个元素的值，然后层层返回对应层两个数的运算结果，直到运算完毕。递归图示如下：

二：递归三大定律

　　1：递归算法必须有个基本结束条件

　　2：递归算法必须改变自己的状态并向基本结束条件演进

　　3：递归算法必须递归地调用自身

根据上述累加例子来简单解释这三大定律。第一条：结束条件可以让算法的递归操作结束。基本的结束条件通常是一个规模小到可以直接解决的问题。如果没有结束条件，那么程序将会进入无限递归，最终导致栈溢出。第二条：递归算法的本质就是将一个大的问题层层剥离，最终使剥离最终结果是一个可以直接解决的问题，然后层层合并最终的到结果。所以递归过程必须向着结束条件的方向推移。第三条：算法必须调用自身，这正是”递归“的定义。递归的逻辑就是利用优美的程序把问题分解为更小更简单的子问题来解决的。

三：热身训练

计算在上述累加（递归方式）过程中，递归次数是多少（假设数据是[1, 3, 5, 7, 9]）？思考递归次数和数据数量的关系。

 1 counter=0 #全局变量记录递归次数
 2 def list_sum(num_list):
 3     global counter
 4     if len(num_list) == 1:
 5         return num_list[0]
 6     else:
 7         counter+=1
 8         return num_list[0] + list_sum(num_list[1:])
 9 
10 print(list_sum([1, 3, 5, 7, 9]))
11 print(counter)