-汉诺塔-递归算法（JS递归函数）
前⾔
递归是⼀种强⼤的编程技术，他把⼀个问题分解为⼀组相似的⼦问题，每⼀问题都⽤⼀个寻常解去解决。递归函数就是会直接或者间接调⽤⾃⾝的⼀种函数，⼀般来说，⼀个递归函数调⽤⾃⾝去解决它的⼦问题。
"汉诺塔"经典递归问题
"汉诺塔"是印度的⼀个古⽼传说，也是程序设计中的经典的递归问题，是⼀个著名的益智游戏：
  题⽬如下：
    塔上有三根柱⼦和⼀套直径各不相同的空⼼圆盘，开始时源柱⼦上的所有圆盘都按从⼤到⼩的顺序排列。⽬标是通过每⼀次移动⼀个圆盘到另⼀根柱⼦上，最终把⼀堆圆盘移动到⽬标柱⼦上，过程中不允许把较⼤的圆盘放置在较⼩的圆盘上；
寻规律（把所有的圆盘移动到C）：
  1）n(圆盘个数) == 1
    第⼀次：1号盘  A -> C      sum(移动次数) = 1
  2）n == 2
    第⼀次：1号盘 A -> B
    第⼆次：2号盘 A -> C
    第三次：1号盘 B -> C  sum = 3
  3）n == 3
    第⼀次：1号盘 A -> C
    第⼆次：2号盘 A -> B
    第三次：1号盘 C -> B
    第四次：3号盘 A -> C
    第五次：1号盘 B -> A
    第六次：2号盘 B -> C
    第七次：1号盘 A -> C  sum = 7
  以此类推...
  故不难发现规律，移动次数为：sum = 2^n - 1　
算法分析（递归）：
  把⼀堆圆盘从⼀个柱⼦移动另⼀根柱⼦，必要时使⽤辅助的柱⼦。可以把它分为三个⼦问题：
    ⾸先，移动⼀对圆盘中较⼩的圆盘到辅助柱⼦上，从⽽露出下⾯较⼤的圆盘，
    其次，移动下⾯的圆盘到⽬标柱⼦上
    最后，将刚才较⼩的圆盘从辅助柱⼦上在移动到⽬标柱⼦上
  把三个步骤转化为简单数学问题：
    （1）    把 n-1个盘⼦由A 移到 B；
    （2）    把 n个盘⼦由 A移到 C；
    （3）    把n-1个盘⼦由B 移到 C；
  我们创建⼀个JS函数，当它调⽤⾃⾝的时候，它去处理当前正在处理圆盘之上的圆盘。最后它回⼀个不存在圆盘去调⽤，在这种情况下，它不在执⾏任何操作。
JavaScript源代码实现
var hanoi = function(disc,src,aux,dst){
if(disc>0){
hanoi(disc-1,src,dst,aux);
console.log(' 移动 '+ disc +  ' 号圆盘 ' + ' 从 ' + src +  ' 移动到 ' +  dst);
hanoi(disc-1,aux,src,dst)
}
}
hanoi(3,'A','B','C')
整个算法的思路是：
1. 将A柱⼦上的n-1个盘⼦暂时移到B柱⼦上
2. A柱⼦只剩下最⼤的盘⼦，把它移到⽬标柱⼦C上
3. 最后再将B柱⼦上的n-1个盘⼦移到⽬标柱⼦C上
JS递归函数遍历Dom
  递归函数可以⾮常⾼效的操作树形结构，在JavaScript有⼀种"天然的树形结构"浏览器端的⽂档对象
模型（Dom）。每次递归调⽤时处理指定树的⼀⼩段。
/*      我们定义⼀个walk_the_DOM函数，
1）它从某个指定的节点开始，按指定HTML源码的顺序，访问树的每个节点
2）它会调⽤⼀个函数，并依次传递每个节点给它，walk_the_DOM调⽤⾃⾝去处理每⼀个节点
*/
var walk_the_DOM = function walk( node , func ) {
func(node);
node = node.firstChild;
while (node) {
walk( node , func );
node = Sibling;
}
}
/*    在定义⼀个getElementByAttribute函数
1）它以⼀个属性名称字符串和⼀个可选的匹配值作为参数
2）它调⽤walk_the_DOM，传递⼀个⽤来查节点属性名的函数作为参数，匹配得节点都会累加到⼀个数组中*/
var getElementsByAttribute=function(att,value){
var results=[];
walk_the_DOM(document.body,function(node){
var deType===1&&Attribute(att);
if(typeof actual==='string' &&( actual===value|| typeof value!=='string')){
results.push(node);
}
});
return results;
}
命名函数表达式和递归
递归问题
求阶乘的函数：
function factorial(num){
if(num<=1){
return 1;
}else{
return num*factorial(num-1);
}
}
通过将函数factorial设置为null，使原始函数的引⽤只剩⼀个,
arguments.callee实现递归
arguments.callee是⼀个指向正在执⾏的函数的指针，因此可以⽤它来实现对函数的递归调⽤
function factorial(num){
if(num<=1){
return 1;
}else{
return num*arguments.callee(num-1);
}
}
var anotherFactorial=factorial;
factorial=null;
anotherFactorial(3) //6
⽤arguments.callee代替函数名，可以确保⽆论怎样调⽤函数都不会出问题。因此，在编写递归函数时，使⽤arguments.callee总⽐使⽤函数名更保险。
但是在严格模式下，不能通过脚本访问arguments.callee，访问这个属性会报错
命名函数表达式实现递归
创建⼀个名为f()的命名函数表达式，然后赋值给factorial，即使把函数赋值给了另⼀个变量，函数的名字f仍然有效，所以递归调⽤照样能正常完成。
这种⽅式在严格模式和⾮严格模式都可⾏。
var factorial =function f(num){
'use strict'
if(num<=1){
return 1;
编程递归函数}else{
return num* f (num-1);
}
}
factorial(3)    //6
var anotherFactorial=factorial;
factorial=null;
anotherFactorial(3)      //6
参考《JavaScript语⾔精粹》

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。