汉诺塔递归算法JS实现

递归把一组问题分解为一组相似的子问题，每一个问题都用一个寻常解去解决。递归函数就是会直接或者间接调用自身的一种函数，一般来说，一个递归函数调用自身去解决它的子问题。在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？，这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。

“汉诺塔问题”描述

塔上有三根柱子和一套直径各不相同的空心圆盘，开始时源柱子上的所有圆盘都按从大到小的顺序排列。目标是通过每一次移动一个圆盘到另一根柱子上，最终把一堆圆盘移动到目标柱子上，过程中不允许把较大的圆盘放置在较小的圆盘上；

汉诺塔示意图
当n=3时的移动如下：

n=3时的汉诺塔问题

把所有圆盘(n个)从A(src)移动到C(dst)。

(1) 当n=1时
第一次：1号 A -> C

(2) 当n=2时
第一次： 1号 A -> B
第二次: 2号 A -> C
第三次： 1号 B -> C

(3) 当n=3时
第一次： 1号 A -> C
第二次： 2号 A -> B
第三次： 1号 C -> B
第四次： 3号 A -> C
第五次： 1号 B -> A
第六次： 2号 B -> C
第七次： 1号 A -> C

可发现移动次数与n的关系为：2^n - 1

算法分析

实现这个算法可以简单分为三个步骤：
(1)把A上的 n-1 个圆盘借助辅助塔(C塔)由A移到B;
(2)把 n号(即最大的那个)由A移到C；
(3)把B上的 n-1 个圆盘借助辅助塔(A塔)由B移到C；

javascript实现

// js语言精粹 4.8递归 汉诺塔问题
var times = 0;
function hanoi(n, src, aux, dist) {
    if (n > 0) {
        hanoi(n - 1, src, dist, aux); //递归，把A(src)塔上编号1~n-1的圆盘移到B(aux)上，以C(dist)为辅助塔
        console.log("第" + (++times) + "次移动：" + n + "号盘从" + src + "移到" + dist); //把A塔上编号为n的圆盘移到C上
        hanoi(n - 1, aux, src, dist); //递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
    }
}
hanoi(3, 'A', 'B', 'C');
//运行结果
第1次移动：1号盘从A移到C
第2次移动：2号盘从A移到B
第3次移动：1号盘从C移到B
第4次移动：3号盘从A移到C
第5次移动：1号盘从B移到A
第6次移动：2号盘从B移到C
第7次移动：1号盘从A移到C

调用方法的栈机制

从主线程开始调用方法（函数）进行不停的压栈和出栈操作，函数的调用就是将函数压如栈中，函数的结束就是函数出栈的过程，这样就保证了方法调用的顺序流，即当函数出现多层嵌套时，需要从外到内一层层把函数压入栈中，最后栈顶的函数先执行结束（最内层的函数先执行结束）后出栈，再倒数第二层的函数执行结束出栈，到最后，第一个进栈的函数调用结束后从栈中弹出回到主线程，并且结束。