裴波那契数列 JavaScript 尾递归实现

一般递归实现：

//经典递归
function fibonacci(n) {
return (function(n) {
if (n == 1 || n == 2)
return 1;
return arguments.callee(n - 1) + arguments.callee(n - 2);
})(n);
}

或者：

function fibonacci(n){

　　if(n<2)

　　return n;

　　else

　　　　return fibonacci(n-1)+fibonacci(n-2);

}

尾递归实现：

//尾递归
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;
}

C# 版：

传统的递归方式如下：

public static int FibonacciRecursively(int n)

{

    if (n < 2) return n;

    return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);

}

而改造成尾递归，我们则需要提供两个累加器：

public static int FibonacciTailRecursively(int n, int acc1, int acc2)

{

    if (n == 0) return acc1;

    return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);

}

巴特西

裴波那契数列 JavaScript 尾递归实现

最新文章

热门文章