文章摘要1、递归算法原理1、递归作用2、递归算法思想3、为什么递归难以理解4、递归应用场景2、一些典型问题的python实现1、阶乘计算2、汉诺威问题3、斐波那契数列问题4、乔迁

对于初学者来说，递归及其派生的动态规划可以说是最难理解的几种算法。 看着别人的代码，你会发现别人递归地解析了几行代码，但让自己写却死活写不出来。

为什么会有这样的反差呢？ 经过长时间的递归学习和代码练习，我们得出结论，因为递归算法的实现思想与我们正常的思维观念不太一致。

一、递归算法的原理1、递归的作用举一个例子来说明。 有一天，你找到了隐藏宝箱。 你用熟练的开锁技巧打开了它。 (不要在意为什么你有熟练的开锁技巧。 )于是，你发现里面有一个大意的蜗牛点藏宝箱，在那里又用熟练的开锁技巧打开，里面有一个更大意的蜗牛点藏宝箱，最后找到一张纸条写的时候，你会在地上的箱子

所谓的递归，就是有递出有归还，即有去有回

打开箱子走了，就不知道一共打开了多少个箱子，活在无限循环的烦恼中。 所以，对于这样的打开箱子的行为，我们只能选择循环，即有去无回

2、递归算法的思想如上所述，递归是指有去有回。

“有时去”是指递归问题必须为分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。 这上面的例子表明所有藏宝箱都可以用同样的开锁技巧打开。

“有回”是指：问题的演化过程，是由大到小、由近到远的过程，有明确的终点(临界点)。 到了这个临界点，就更小了，不需要去很远的地方。 最后，从这个临界点开始，原路返回到原点，原问题解决上例临界点是"哈哈"备忘录。 最后一个箱子的数量回到了原点的答案。

3、为什么递归很难理解上面的例子，大家不是很理解吗？ 为什么做题的时候很辛苦呢？

因为递归的想法和通常的想法相反。

在确定递归计算是否正确时，保罗Graham采用一种方法，即，

如果以下两点成立，就表明这个递归对所有n都是正确的。

a、n=0、1时，结果正确

b .假设递归对n正确，同时也假设对n 1正确。

咦，这不是数学归纳法吗？ 这有什么困难？

在数学归纳法中，知道a后多验证b，由于数量少的问题，要验证从下往上。

但是，在递归算法中，首先从最大问题逐渐分解为小问题进行处理，在从上往下中进行验证。

我们用一个计算阶乘n！ 请看代码示例

这是思维习惯的不适应，适应了就没关系。 说白了，多练习一下。

但是，开始练习的时候该怎么办？

容易做！ 直接作为函数调用，多调用，你也会的。

4、递归应用场景只要满足以下两个条件就可以应用。

1、大问题可以分解成小问题，有同样的解法

2、有终止条件，不会无限循环。

2、汉诺威问题有三座塔a、b、c。 a塔有n个穿孔圆盘，盘子尺寸从上到下依次增大，b、c塔为空。 按照以下规则要求所有圆盘移动到c塔，一次只能移动一个圆盘； 大盘不能叠在小盘上。

问：怎么移动？ 最少移动几次？

（看完问题先别急着看代码，先自己写写试试，看到这里其实你也已经能写出大概的代码了）
斐波拉契数列，是这样的一个数列：0、1、1、2、3、5、8、13、21、……。
斐波拉契数列的核心思想是:

要求:利用递归算法获得指定项的斐波拉契数列。