递归和递推：javascript求斐波那契数列的尾递归方法(转载)

刚才在IBM DW上看到这篇《JavaScript 技巧与高级特性》，其中关于arguments.callee的部分有一个用递归来求斐波那契数列的例子，简化一下是这样的：

//经典递归
function fibonacci(n) { 
    return (function(n) { 
        if (n == 1 || n == 2) 
            return 1;
        return arguments.callee(n - 1) + arguments.callee(n - 2);
    })(n);
} 
 
fibonacci(4); //result: 3
fibonacci(5); //result: 5
fibonacci(10); //result: 55

这种教科书式的写法出镜率很高，在很多文章里都可以看到，但是速度也特别慢，曾经看到过有些人就拿这种例子来说明“递归的效率低”或者“用javascript做函数式编程效率低”，然后给出迭代的写法……

更新：我今天老老实实的读了SICP的第一章之后发现书中对这个问题其实有很严谨的解释，为了防止自己被骂成民科，赶紧修正了一些说法，加了下划线的文字都是有错误的，新增加的文字用红褐色。

其实这个方法速度慢并不是函数式编程（FP）的错，首先要把词义弄清楚，真正的数学意义上的“递归”（recursive）包含了“递推”（recurrence）和“回归”（regression）的过程，在程序执行的过程中，“递归”（recursive）指的是一种方法，把大的复杂的问题分解成更小更简单的问题，逐级分解下去，直到问题的规模小到可以直接求解，然后再逐级向上回溯直到解决最初的问题，用程序来实现这种算法的时候至少包含一次以上的递推执行过程，效率当然比不上直接作一次迭代。递归的计算过程（recursive process）包含了两个阶段，先逐级扩展（expansion），构造起一个由被推迟的操作组成的链条（会被解释器保存在堆栈里），然后在收缩（contraction）阶段逐级回溯执行那些操作。随着递归计算步骤的增多，这种方法消耗的资源会越来越大，而且会包含越来越多的冗余操作，上面那个求斐波那契数列的例子（在SICP里被称作“树形递归”）在这方面问题尤其严重，因为它的计算步骤会随着参数而指数性的增长。

引用SICP上的图解：
scip

而在编程里常说的递归其实就是简单的指“自己调用自己”的过程，指的是一种语法形式，而不是计算过程，在SICP里使用“递归过程”（recursive procedure）这个词来称呼，表示“一个过程的定义中引用了该过程本身”，在FP里就是一个函数把状态作为参数反复调用自己，来实现迭代的效果，所以未必需要递推一次以上。，用递归过程也可以产生出迭代计算过程（iterative process，迭代计算过程中消耗的资源是一个常量），递归==迭代，这个表达式不仅在lisp,Erlang这类FP语言里成立，在javascript里也一样。

比如那个求斐波那契数列的例子就可以用尾递归：

//尾递归
function fibonacci(n) { 
    return (function(n1, n2, i) { 
        return ( i < n ) ? arguments.callee(n2, n1+n2, i+1) : n1;
    })(1,1,1);
}

跟这样的迭代方法是完全等价的：

//等价的循环
function fibonacci(n) { 
    var n1 = n2 = s = i = 1;
    for(; i<n; i++){
        s = n1 + n2;
        n1 = n2;
        n2 = s;
    }
    return n1;
}

速度测试：

都是从数列的起始处开始递推，区别只是：在迭代方法里是把每两个相邻的数相加的和保存在循环体外部的局部变量里，在尾递归方法中是把这个和作为参数传给下一次函数调用。

附带说一下，“尾递归”（Tail Recursion）指的是把计算过程集中在函数递归调用的最后一次把每次函数递归调用中的所有运算结果或操作都逐步传递到最末尾一次的函数调用，FP语言在编译/解释的时候都会把尾递归优化成一次直接的运算，而在javascript引擎里就算没有优化，至少也可以在每次调用过程中不留下任何痕迹，可以像普通的循环语句那样线性的推算到最后，因此无论速度还是内存消耗，都跟普通的迭代方法没有区别。

原文链接：http://www.limboy.com/2008/11/22/javascript-tail-recursion/