算法入门总结（五）—— 递归

算法入门总结（五）—— 递归

递归是学习算法时绕不开的一道坎，而递归算法本身用起来也是十分方便，所以特别拿出来进行总结。

先看一个递归实例热热身 —— 阶乘函数

long f(long n) {return n == 0 ? 1 : f(n-1) * n;
}

对于递归问题，理解的重点在于放弃，放弃跟踪递归全程的企图，只需理解递归的条件、两次递归之间的事件以及递归结束的条件，把递归问题展开纯属自讨苦吃。

下面举一个使用递归解决的经典问题——汉诺塔问题（Hanoi）

原问题是这样的：

在印度，有一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片，一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一概针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。问至少需要多少步才能完成这个操作。

当然，在现实中我们没有办法模拟出64片金片的移动，因为这个次数是以亿亿次为数量级的，用我们目前常见的电脑模拟的话大概需要数十万年。所以我们将问题简化为5片金片。

问题就大致简化为：

有三根柱子 A, B, C，A 柱上自大而小叠有5片金片，将它们全部移动到 C 柱，问最少需要多少步？

刚拿到这道题时可能感觉无从下手，但我们可以将问题简化一下——如果只有两片金片，你会怎么做？

如果只有两片，首先我们会把小的先移动到 B 柱，再将大的移动到 C 柱，最后把小的移动到 C 柱，即可完成任务。

那么，如果有三片呢？

如果有三片，根据刚才的思路，我们会先想办法把上面两片小的移到 B 柱，再将大的移动到 C 柱，最后把两片小的移动到 C 柱，任务完成！

那怎么把上面两片小的移到 B 柱呢？

这时我们会发现，最大的一片对于上面两小片来说相当于是不存在的（小片可任意压于大片之上），那这个问题又神奇地变成了只有两片的问题，只是目标柱从 C 变成了 B 。

到这里我们总结一下：汉诺塔问题永远只有三步！

1、将除最下面一层之外的所有层移到辅助柱

2、将最下面一层移到目标柱

3、将其余层移到目标柱

有趣的是，上面的第一步又可分为三步来实现：

1、将除最下面一层之外的所有层移到辅助柱

2、将最下面一层移到目标柱

3、将其余层移到目标柱

而第一步又可分为三步来实现......

至此，我们已经明显发现递归的存在，而汉诺塔问题的经典解决方案就是使用递归算法，下面直接给出代码：

#include <cstdio>int step = 0; //记录移动的步数/** paras* n:需要移动的层数* from:移动该柱的金片* buffer:辅助柱* to:目标柱*/
void hanoi(int n, char from, char buffer, char to) {if(n == 1) //2、将最下面一层移到目标柱printf("No.%d: from %c to %c.n", ++step, from, to);hanoi(n-1, from, to, buffer); //1、将除最下面一层之外的所有层移到辅助柱printf("No.%d: from %c to %c.n", ++step, from, to);hanoi(n-1, buffer, from, to); //3、将其余层移到目标柱
}int main() {int n;scanf("%d", &n); //输入总层数hanoi(n, 'A', 'B', 'C');return 0;
}

对于递归问题，其实就是以下思路：对于问题 n，如果问题 n-1 已经解决了，那么 n 则很容易解决。

这就类似于数学中的数学归纳法，要想证明 n > 1 时是否成立，只需证明 1) n == 1 时成立，2)若 n == k-1 时成立，则 n == k 时也成立。我们没必要从1开始逐一验证每个自然数，只要证明了“基础条件”、再证明了“递推条件”，大自然的规律会帮我们搞定一切。

换句话说，我们的任务就是：

1、写程序告诉电脑“如何分解一个问题”

2、写程序告诉电脑“当该问题分解到最简时如何处理”

那么，具体“如何递推、如何回归”这个简单问题就不要再操心了，电脑自己能搞定。

（注：本文部分解答来自知乎用户 Fireman A、郭风林以及一位匿名用户，感谢几位大神！）