什么是递归函数

递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层。递归函数必须有结束条件。

当函数在一直递推，直到遇到墙后返回，这个墙就是结束条件。所以递归要有两个要素，结束条件与递推关系。

注:递归的时候，每次调用一个函数，计算机都会为这个函数分配新的空间，这就是说，当被调函数返回的时候，调用函数中的变量依然会保持原先的值，否则也不可能实现反向输出。

从概念上出发，给出以下的例子：

function foo(){
    console.log("函数 foo 是递归函数。");
    foo();
}

这个例子的 foo 函数就是一个递归函数。

当你把这个函数拿到浏览器上运行的时候，你会发现内存溢出了，为什么呢？因为这个递归函数没有停止处理或运算的出口，因此
这个递归函数就演变为一个死循环。

那如何使用递归呢？

使用递归函数必须要符合两个条件：

1、 在每一次调用自己时，必须是（在某种意义上）更接近于解；

这句话怎么理解？大家家里都有楼梯吧？比如从一楼走到二楼，那么我们的起点是一楼，目的地是二楼，当你往上每走一个台阶是不是越接近二楼，也就是越接近目的地。

因此这句话可以这样理解：函数每一次调用自己时，就越接近于我们期望它完成的任务的终点。

2、必须有一个终止处理或计算的出口。

这句话的意思是：必须要有一个标准的标志，让函数结束调用函数自身。
比如，怎么知道你已经走到二楼了呢？当你看到有个门，门牌上写着 2F 的，然后推开它跨过去，那么你就到二楼了。

递归案例

递归阶乘函数的实现，（阶乘的含义：一个正整数的阶乘（英语：factorial）是所有小于及等于该数的正整数的积，并且有0的阶乘为1。自然数n的阶乘写作n!。）

写法一：

function test(num){
    if(num <=1){
        //递归停止的条件，必须得需要
        return 1;
    }
    else{
        //调用递归
        return num * test(num-1);
    }
}

缺点：如果把test方法保存到一个变量，再释放test方法，使指向原始函数的引用只剩下变量。会报错。

如下：

写法二：

function test(num){
    if(num <=1){
        //递归停止的条件，必须得需要
        return 1;
    }
    else{
        //调用递归,使用arguments.callee的方法代替函数名
        return num * arguments.callee(num-1);
    }
}

优点：arguments.callee指向一个正在执行的函数的指针。可以解决写法一中的缺点。

缺点：严格模式下，不支持arguments.callee。

写法三

var test = (function f(num){
    if(num <=1){
        //递归停止的条件，必须得需要
        return 1;
    }
    else{
        //调用递归
        return num * f(num-1);
    }
});

可以解决写法一、写法二中的问题 。

使用建议：

在使用递归时，要注意对递归函数的参数类型的检查，一定要保证有一个终止处理或计算的出口。否则很容易演变为死循环，从而造成内存溢出。

链接: https://fly63.com/article/detial/10843