link

2015-10-16 23:01

Fibonacci Sequences in JavaScript with/without recursive

本文作者:IMWeb link 原文出处:IMWeb社区 未经同意,禁止转载

介绍几种使用javascript实现斐波那契数列的方法。

其中第一种和第二种都是使用递归:(可优化,应该将每一个元素的值缓存起来,而不是每次递归都计算一次)

        //with Recursion 
        function fibonacci1 (argument) {
            // body...
            return (argument <= 1 ? argument : fibonacci1(argument - 1) + fibonacci1(argument - 2));
        }
        window.console.log(fibonacci1(10));

        function fibonacci2 (argument) {
            return (argument <= 1 ? argument : arguments.callee(argument - 1) + arguments.callee(argument - 2));
        }
        window.console.log(fibonacci2(10));

这里可以说一下JS函数实参对象的callee属性。JS函数的实参对象定义了calleecaller属性。在ES5严格模式中,对这两个属性的读写操作都会产生一个类型错误(TypeError)。而在非严格模式下,ES标准规范规定callee属性指代当前正在执行的函数。caller是非标准的,但大多数浏览器都实现了这个属性,它指代调用当前正在执行的函数的函数。通过caller属性可以访问调用栈。callee属性在某些时候会非常有用,比如在匿名函数中通过callee来递归地调用自身。

var factorial = function (x) {
    if (x == 1) {return 1;}
    return x * arguments.callee(x-1);
};

第三种用的非递归。

        //without Recursion 
        function fibo3 (argument) {
            if(argument <= 1){
                return argument;
            }
            var fibo = 1;
            var fiboPre = 1;
            for (var i = 2; i < argument; ++i) {
                var temp = fibo;
                fibo = fibo + fiboPre;
                fiboPre = temp;
            }
            return fibo;
        }
        window.console.log(fibo3(10));

第四种也是非递归,但是利用了黄金比率1.618,不过要注意的是这种方法在n>69之后,性能就会下降很快,参考文章看这里:http://www.mathsisfun.com/numbers/fibonacci-sequence.html

        //with gold ratio
        function fibo4 (n) {
            var sqrt5 = Math.sqrt(5);
            var alpha = (1+sqrt5)/2; // 黄金比率:1.618...
            return Math.round(Math.pow(alpha,n) / sqrt5); // Please note that this method holds good till n = 69 only.http://www.mathsisfun.com/numbers/fibonacci-sequence.html
        }
        window.console.log(fibo4(3));
0条评论

    您需要 注册 一个IMWeb账号或者 才能进行评论。