Python递归详解

大家好，又见面了，我是你们的朋友全栈君。

递归的依据在数学中，其实就是数学中的数学归纳法。

一、数学归纳法

什么是数学归纳法？

最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：

证明当n= 1时命题成立。 假设n=m时命题成立，那么可以推导出在n=m+1时命题也成立。（m代表任意自然数）

这种方法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺效应也许更容易理解一些。例如：你有一列很长的直立着的多米诺骨牌，如果你可以：

1. 证明第一张骨牌会倒。
2. 证明只要任意一张骨牌倒了，那么与其相邻的下一张骨牌也会倒。

思考：怎么证明所有人都是秃子？

• 我们知道有0根头发的人是秃子，有1根头发的人也是秃子；
• 假设有n根头发的人是秃子，那么有n+1根头发的人也是秃子；
• 所以，所有人都是秃子；

二、什么是递归

所谓递归，简单点来说，就是一个函数直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

我们可以把” 递归 “比喻成 “查字典 “，当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词。

可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。（摘自知乎的一个回答）

我们以阶乘为例：

def Factorial(n):
    if n==0:
        return 1
    return n*Factorial(n-1) 

三、递归和栈的关系

常常听到 “递归的过程就是出入栈的过程”，这句话怎么理解？比如以上面的阶乘例子为例：求n=3，递归过程如下：

第 1~4 步，都是入栈过程，Factorial(3)调用了Factorial(2)，Factorial(2)又接着调用Factorial(1)，直到Factorial(0)。

第 5 步，因 0 是递归结束条件，故不再入栈，此时栈高度为 4，即为我们平时所说的递归深度；

第 6~9 步，Factorial(0)做完，出栈，而Factorial(0)做完意味着Factorial(1)也做完，同样进行出栈，重复下去，直到所有的都出栈完毕，递归结束。

四、如何思考递归

递归的思维方式和我们正常的推理方式是相反的。

那我们怎么判断这个递归计算是否是正确的呢？Paul Graham 提到一种方法，如下：

如果下面这两点是成立的，我们就知道这个递归对于所有的 n 都是正确的。

1. 当 n=0,1 时，结果正确；
2. 假设递归对于 n 是正确的，同时对于 n+1 也正确。

汉诺塔展开问题

问题描述为：有三根杆子 A，B，C。A 杆上有 N 个穿孔圆盘，盘的尺寸由上到下依次变大，B，C 杆为空。要求按下列规则将所有圆盘移至 C 杆：

1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。

问：如何移？最少要移动多少次？

首先看下基本情况，即终止条件：N=1 时，直接从 A 移到 C

再来看下通用情况：当有 N 个圆盘在 A 上，我们已经找到办法将其移到 C 杠上了，我们怎么移动 N+1 个圆盘到 C 杠上呢？很简单，我们首先用将 N 个圆盘移动到 C 上的方法将 N 个圆盘都移动到 B 上，然后再把第 N+1 个圆盘（最后一个）移动到 C 上，再用同样的方法将在 B 杠上的 N 个圆盘移动到 C 上，问题解决。

代码如下：

def Han(n,a,b,c):
    if n ==1:
        print('a--->c')
    else:
        Han(n-1,a,c,b)# 如果想要移动n个盘子到指定目的，那么一定要先将n-1个盘子移动到备用柱上
        print('a--->c')
        #剩下待处理的盘子还有n-1个
        #此时盘子已经在B上而不是在A上
        #让第n-1个盘子从B移动到C
        Han(n-1,b,a,c)   

五、什么时候用递归

问题可用递归来解决需具备的条件：

1. 子问题需与原问题为同样的事，且规模更小；
2. 程序停止条件。