基础算法 | 递归的世界你不懂.......

转眼间又到了深夜，终于能好好吃一把鸡了。

…………

等等，TM11点就停电了。玩鸡毛！！！

哦……那么，就只能……学习了……

今天学啥呢？

对，没错

今天要教给大家的是

递（zhuang）归（bi）大法

本节纲要：

- 什么是递归

- 递归函数的工作原理

- 经典的递归问题

- 递归的一些适用情况

什么是递归？

在此之前，让老衲来引用一句名言：

迭代的是人，递归的是神

–L. Peter Deutsch

那么，何为递归呢？别急，听老衲慢慢为施主道来。

所谓递归（recursion）：

说白了就是子程序（或函数）直接调用自己或间接调用自己的一种基本方法。运用递归通常可以把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，从而减少程序的代码量。

递归调用的形式：

-直接调用：即在函数中调用函数本身。

举个栗子，下面一段代码用于求斐波那契数列的第N项：

- 间接调用：指A函数执行中调用了B函数，而B函数又调用了A函数。

还是再举个栗子吧。

当然，这是一个死递归，没有出头之日的。

简单介绍了递归，下面开始我们的重头戏。

递归的工作原理：

- 先谈谈递归函数的内部执行过程：

1. 开始时，系统先为递归调用设立一个工作栈，它的结构包括值参、局部变量和返回地址。
2. 每次执行递归调用时，系统会把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈。
3. 每次递归调用结束后，将栈顶元素出栈，然后转向返回地址指定的位置继续执行。

这里关于栈的内容暂时不过多赘述，大家可以自行上网找资料查询。其实说白了递归调用的本质还是函数调用，那函数调用必然会遵循一个原则：被调用的函数会复制一个副本，为调用者服务，而不受其他函数的影响。

很多人把递归理解为一种代码反复循环使用。其实这是有失偏颇的。像前面说的，一个函数func被调一次，他就在内存中复制一份代码，再调用，再复制。然后根据内存的栈式管理返回退出。你也可以把被递归调用各个函数当作不同名的函数，这样更便于理解。

- 下面来结合一个求阶乘的例子来讨论一下这个过程：

先假设我们在main函数里面传入的num=3吧。

1.一层执行到res=3*factorial(3-1);停止,执行二层factorial (3-1),也就是factorial (2)

2.二层执行到res=2*factorial(2-1);停止,执行三层factorial (2-1),也就是factorial (1)

3.三层执行到if(num==1) res=1;然后return(res)到二层的factorial (2-1)的位置，二 层继续执行

4.二层执行res=1*2;然后就return(res)到一层factorial (3-1)的位置，一层继续执行

5.一层执行res=2*3;然后就return(res)到了最初调用factorial (3)的main函数里。所以就得到结果为6

整个过程大体就是这样的。

函数的执行流程：

递归的经典问题

汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

在学习了上面的递归原理之后，这里是不是想动手AC一下这道题呢？

假如有ABC三根柱子，先假设A柱子只有３个盘子的情况。盘子从上到下依次编号为１２３.我们可以先把１和２号盘子借助C柱子，移动到B柱子上，然后在将３号盘子移动到C柱子上。然后再借助A柱子，将１和２号盘子移动到C柱子上，done！至于怎么把１和２号盘子借助C移到B柱子上，想必也不用多说。

那么，假如有N个盘子，我们只需要借助C柱子，将１到N－１号盘子移动到B柱子上，再将N号盘子移动到C上，再将1到N-1号盘子移动到C上，done！而借助C柱子移动1到N-1号盘子到B柱子，又只需要考虑将1到N-2号盘子借助B移到C上，最后再从C里移动回来。这样我们就不断将问题缩小了。卧槽是不是有点晕，那就对了。

算法描述：

当A柱子只有一个盘子的时候，只需要从将A柱子上的一个盘子移到C塔上。

- 当A柱子上有两个盘子是，先将A柱子上的1号盘子（编号从上到下）移动到B柱子上，再将A柱子上的2号盘子移动的C柱子上，最后将B柱子上的小盘子移动到C柱子上。

- 当A柱子上有3个盘子时，先将A柱子上编号1至2的盘子（共2个）移动到B柱子上（需借助C柱子），然后将A柱子上的3号最大的盘子移动到C柱子，最后将B柱子上的两个盘子借助A塔移动到C柱子上。

- 当A柱子上有n个盘子是，先将A柱子上编号1至n-1的盘子（共n-1个）移动到B柱子上（借助C柱子），然后将A柱子上最大的n号盘子移动到C柱子上，最后将B柱子上的n-1个盘子借助A柱子移动到C柱子上。

综上所述，除了只有一个盘子时不需要借助其他柱子外，其余情况均一样的。

好，又到了激动银心的看代码时间：

关于递归的适用情况：

递归通常用来解决结构自相似的问题。所谓结构自相似，就是说在结构上组成相似的，可以采用同一种方法去解决。具体地，整个问题的解决，可以分为两部分：第一部分是一些特殊情况，有直接的解法；第二部分与原问题相似，但比原问题的规模小。实际上，递归就是分而治之的思想，把大问题化为小问题，再把小问题化为更小的问题，在解决这样一个个的小问题之后，大问题自然迎刃而解。

因此，递归有两个基本要素：

（1）边界条件：确定递归到何时终止，也称为递归出口。

（2）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果。

-The End-

编辑 / 邓发珩

指导老师 / 秦时明岳

注：部分资料来源网络。作者为优化突击队成员，

如有疑问，欢迎咨询：邓发珩 （华中科技大学本科一年级、联系方式：2638512393@qq.com、个人公众号：程序猿声）秦虎老师（professor.qin@qq.com）