JavaScript函数的特性与应用实践深入详解(4)
8 递归
递归函数是会直接或间接地调用自身的函数。它会把一个问题分解为一组相似的子问题，而每一个子问题都会用一个寻常的解来解决。
汉诺塔的游戏规则是：塔上有 3 根柱子和一套直径不相同的空心圆盘。开始时，源柱子上的所有圆盘都是按照从小到大的顺序堆叠的。每次可以移动一个圆盘到另一个柱子，但不允许把较大的圆盘放置在娇小的圆盘之上。最终的目标是把一堆圆盘移动到目标柱子上。我们可以用递归解决这个问题：
/**
* 汉若塔
* @param disc 圆盘编号
* @param src 源柱子
* @param aux 辅助用的柱子
* @param dst 目的柱子
*/
var hanoi = function (disc, src, aux, dst) {
if (disc > 0) {
hanoi(disc - 1, src, dst, aux);
console.log('Move disc ' + disc + ' from ' + src + ' to ' + dst);
hanoi(disc - 1, aux, src, dst);
}
};
hanoi(3, 'Src', 'Aux', 'Dst');
这里演示了如果圆盘数为 3 的解法：
这个问题可以分解为 3 个子问题。首先移动一对圆盘中较小的圆盘到辅助的柱子上，从而露出下面较大的圆盘；然后再移动下面的圆盘到目标柱子。最后再将较小的圆盘从辅助柱子再移动到目标柱子上。通过递归调用自身来处理圆盘的移动，就可以解决这些子问题。
上面这个函数最终会以一个不存在的圆盘编号被调用，但它不执行任何操作，所以不会导致死循环。
递归函数可以非常高效地操作树型结构。比如文档对象模型（DOM）,我们可以在每次递归调用时处理指定树的一小段：
/**
* 从某个节点开始，按照 HTML 源码中的顺序，访问该树的每一个节点
* @param node 开始的节点
* @param func 被访问到的每一个节点，会作为参数传入这个函数，然后这个函数被调用
*/
var walk_the_DOM = function walk(node, func) {
func(node);
node = node.firstChild;
while (node) {
walk(node, func);
node = node.nextSibling;
}
};
/**
* 查找拥有某个属性的元素
* @param att 属性名称字符串
* @param value 匹配值（可选）
* @return 匹配的元素数组
*/
var getElementsByAttributes = function (att, value) {
var results = [];
walk_the_DOM(document.body, function (node) {
var actual = node.nodeType === 1 && node.getAttribute(attr);
if (typeof actual === 'string' && (actual === value) || typeof value != 'string') {
results.push(node);
}
});
return results;
};
注意： 深度递归的函数会因为堆栈溢出而运行失败。比如一个会返回自身调用函数结果的函数，它被称为尾递归函数。