递归

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])便是最小子问题）：

递归的原则

​ 从上面的例子中能够总结出关于递归的三个原则：

• 递归算法必须有基本情况；
• 递归算法必须改变其状态并向基本情况靠近；
• 递归算法必须递归地调用自己。