递归
1. 递归
递归是数据结构中也是我们平时写代码的时候非常常用的一种思想，通过递归可以将问题不断地分成更小的子问题，直到子问题能够用普通的方法解决，通常情况下，递归会使用一个不停调用自己的函数来实现。
有很多人会将循环和递归放在一起做比较，下面通过一个小案例来看一下递归和循环的差别。
举个例子：计算[1,2,3,4,5]的加和。
使用循环
count = 0
numList = [1, 2, 3, 4, 5]
for i in numList:
count += i
count
# 输出
15循环过程
使用循环的时候，每次会从列表中提取出一个元素加到之前元素求得的和上，等到循环结束后所有的元素也就被依次的加上了。具体的内部流程如下图所示：
使用递归
def listSum(numList):
if len(numList) == 1:
return numList[0]
else:
return numList[0] + listSum(numList[1:])
numList = [1, 2, 3, 4, 5]
listSum(numList)
# 输出
15递归过程
不难发现，递归是由一个函数体来实现的，而在函数的内部又在调用该函数的本身，其实这也是递归的本质（重复的调用自己），当函数中的条件不足以调用自己的时候，便是我们要找的那个“最小子问题”（能够用最普通方法解决的问题），我们通过先解决这个“最小子问题”然后再去解决稍大一点的问题，以此类推我们能够找到一个解决问题的公式，重复调用这个公式最大的问题就很容易解决了。递归的内部流程图下（Sum([5])便是最小子问题）：
递归的原则
从上面的例子中能够总结出关于递归的三个原则：
- 递归算法必须有基本情况；
- 递归算法必须改变其状态并向基本情况靠近；
- 递归算法必须递归地调用自己。
