JS递归实现阶乘和菲波那切数列

fushuxin 2018-12-18 原文

当我们需要使用递归来完成某些操作的时候，我们先要了解什么是递归

什么是递归？

递归，就是在运行的过程中调用自己。

一般来说，递归需要有边界条件、递归前进段和递归返回段。

当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

举个例子：

1 function fun(){
2                 console.log(new Date())
3                 setTimeout(fun,1000)
4             }
5             fun()

第5行调用fun，fun内的一次定时器每隔1s再调用fun，在函数内部调用自己，这就是递归。

跟循环相同的是，递归是需要有边界条件的，否则就变成了死循环。

递归-阶乘

1 function fun(n){
2                 if(n == 1 || n == 0){
3                     return 1;
4                 }
5                 return n * arguments.callee(n-1)
6             }
7             console.log(fun(10))

设置了if语句为递归限制了边界。

上面我运用了arguments.callee，那什么是arguments.callee呢？

arguments 的主要用途是保存函数参数，但这个对象还有一个名叫 callee 的属性，返回正被执行的 Function 对象，也就是所指定的 Function 对象的正文，简单点就是指代的就是这个函数的本身，这有利于匿名函数的递归或者保证函数的封装性。

利用 callee 的属性，返回正被执行的 Function 对象的方法，使得可以得到阶乘的结果。

需要注意的是：

现在已经不推荐使用arguments.callee()；

原因：访问 arguments 是个很昂贵的操作，因为它是个很大的对象，每次递归调用时都需要重新创建。影响现代浏览器的性能，还会影响闭包。

当然第二种方法就是

1 function fun(n){
2                  if(n == 1 || n == 0){
3                      return 1;
4                  }
5                 return n * fun(n-1)
6             }
7             console.log(fun(10))

arguments.callee用fun取代，一样可以实现递归的效果。

递归-菲波那切数列

菲波那切数列{1，1， 2， 3， 5， 8， 13， 21， 34 …}

可理解为 fun(n) = fun(n-1) + fun(n-2)

当前的值等于前两个数的和。

function fun(n){
                if(n == 1 || n == 2){
                    return 1;
                }
                return fun(n-1) + fun(n-2)
            }
            console.log(fun(9))

同样为递归设置了边界，输出第9位的数值。

以上是个人对于递归的理解，欢迎广大博友的指正和补充