递归（二）—— 初识暴力递归

如何理解暴力递归？

字面意思就是——“暴力的递归”，就是——“别纠结细节，开整（递归）！”

暴力递归就是尝试。即：只要满足递归条件就不断的递归下去，直到达到base case，结束递归。

暴力递归的思想

1. 把问题转化为规模缩小了的同类问题的子问题；

2. 有明确的不需要继续进行递归的条件（也就是base case）；

3. 有当得到了子问题的结果之后的决策过程；

4. 不记录每一个子问题的解；

题目

题目1: 汉诺塔问题

汉诺塔（焚天塔）问题是一个经典的数学谜题，涉及到三个柱子和一系列不同大小的盘子。最初，所有盘子都按照从小到大的顺序叠放在一个柱子上。最大的盘子在最下方。目标是将这些盘子移动到另一个柱子上，同时保持它们的原有顺序，并且在任何时候都不能将较大的盘子放在较小的盘子之上。

题目分析

汉诺塔是典型的利用递归思想解决的问题。下面我们给出具体的数字，通过画图来分析问题。假设当前的汉诺塔是3层，叠放在最左边的柱子上，目标是大小顺序不变的叠放在最右边的柱子上。

如果我们手边就有这样一套汉诺塔玩具，手动的来操作一下，怎么做呢？

第一步：将1号放在右侧；

第二步：将2号放在中间；

第三步：将1号放在中间；

第四步：将3号放在右侧；

第五步：将1号放在左侧；

第六步：将2号放在右侧；

第七步：将1号放在右侧

经过实际操作可是，如果有3个盘子，那么需要7步就可以满足题目要求，可是如果是未知的N个盘子呢？为了实现这个目的，我们按照“把大象放冰箱”的逻辑，只需三步即可：

第一步，将1～n-1号盘子看作整体，移到辅助柱子（中间柱子）上；

第二步，将N号盘子移到最右侧柱子；

第三步，将被移到辅助柱子上1～n-1号盘子再移到最右侧柱子。

这个思路的代码实现就是代码段1.

代码实现

//代码段1
void leftToRight(int n) {
    if (n == 1) {
        printf("move 1 from left to right\n");
        return;
    }

    leftToMid(n - 1);
    printf("move %d from left to right\n", n);
    midToRight(n - 1);
}

代码分析：

函数leftToRight 就是按照冰箱三步法的思路写的，当n == 1时，表示只有一个盘子，不用纠结，直接放到目的地最右侧即可，当n>1 时，将1~n-1的盘子放到中间柱子，即函数leftToMid, 然后将第n个盘子放在最右侧，最后将中间柱子上的盘子放在最右侧，函数midToRight。

函数leftToRight 的逻辑很容易理解，接下来完成 leftToMid 和midToRight 的函数逻辑。

void leftToMid(int n):

这个函数的作用是将盘子从左侧移到中间,也就是冰箱逻辑的的第一步（“第一步，将1～n-1号盘子看作整体，移到辅助柱子（中间柱子）上”），但是这个移动过程的思维逻辑又是一个冰箱三步法，即：

第一步：将左侧的盘子1~ ${n}'$ -1 的部分先移动到辅助柱子，此时的辅助柱子是右侧柱子，

第二步：将第 ${n}'$ 个盘子移动中间；

第三步：将1~ ${n}'$ -1再移到中间柱子，需要函数 rightToMid。

void midToRight(int n):

同样的逻辑，第一步将1~ ${n}'$ -1 移到辅助柱子，此时的辅助柱子是左侧柱子，此时需要midToLeft函数，第二步，将第 ${n}'$ 个盘子从中间移到右侧，第三步将1~ ${n}'$ -1个盘子从左侧移到右侧

//代码段2
void leftToMid(int n) {
    if (n == 1) {
        printf("move 1 form left to mid\n");
        return;
    }
    leftToRight(n - 1);
    printf("move %d form left to mid\n", n);
    rightToMid(n - 1);
}

void midToRight(int n) {
    if (n == 1) {
        printf("move 1 form mid to right\n");
        return;
    }
    midToLeft(n - 1);
    printf("move %d from mid to right\n",n);
    leftToRight(n-1);
}

rightToMid 函数和midToLeft函数还没有定义，按照相同的思路，完成代码。

//代码段3
void rightToMid(int n) {
    if (n == 1) {
        printf("move 1 form right to mid\n");
        return;
    }
    rightToLeft(n - 1);
    printf("move %d form rihgt to mid\n", n);
    leftToMid(n - 1);
}

void midToLeft(int n) {
    if (n == 1) {
        printf("move 1 form mid to left\n");
        return;
    }
    midToRight(n - 1);
    printf("move %d from mid to left\n", n);
    rightToLeft(n-1);
}

void rightToLeft(int n) {
    if (n == 1) {
        printf("move 1 frome right to left\n");
        return;
    }
    rightToMid(n - 1);
    printf("move %d from right to left\n",n);
    midToLeft(n - 1);
}

写完所有的调用过程，发现每一个子过程都要调用另外两个子过程，循环嵌套，将完整的函数调用补充完成，运行程序。

#include <stdio.h>

void leftToRight(int n);
void leftToMid(int n);
void rightToLeft(int n);
void rightToMid(int n);
void midToLeft(int n);
void midToRight(int n);

void hanoi_1(int n){
    leftToRight(n);
}

int main(){
    hanoi_1(3);
    return 0;
}

运行结果

上图的运行结果与之前我们手动操作的结果是一致的。

代码优化

我们用了6个子过程完成了题目要求，但这么写代码的弊端是显而易见的，就是过于冗余复杂，其实6个子函数的逻辑是一样的，每个子过程都涉及三个柱子，即当前柱子，目的柱子和辅助柱子，只不过在6个子过程中这三个柱子所代表的柱子标号不一样。但是逻辑是一样的；

第一步：1～n-1从当前柱子到辅助柱子

第二步：n从当前柱子到目的柱子

第三步：1～n-1从辅助柱子到目的柱子

#include <stdio.h>

void hanoi_2(int n, const char* from, const char* to, const char* other){
    if(n == 1){
        printf("move 1 from %s to %s\n", from, to);
        return;
    }
    hanoi_2(n-1, from, other, to);
    printf("move %d from &s to %s\n", n, from, other);
    hanoi_2(n-1, other, to, from);
}

int main(){
    printf("call hanoi_2\n");
    hanoi_2(3,"left","right","mid");
}

运行结果：