Javascript 递归函数

当一个函数在执行时调用了自身，那么这个函数就是递归函数。递归函数经常用来解决一些循环反复的问题。我们首先列举一些递归函数的使用场景。

使用场景

阶乘

如果我们要求得 1*2*3*4*5*6 的结果，可以构造一个如下函数：

function factorial(n) {
    if(n === 1) return 1;
    return n*factorial(n-1);
}
factorial(6); //720    

斐波拉契数列

一只兔子，从出生起第三个月会生一只兔子，求第n月的兔子总数。每个月的兔子总数数列大概是这个样子：

1 1 1+1(2) 2+1(3) 3+2(5) 5+3(8) ...

即每个月兔子的总数为：
上个月兔子总数+上上个月兔子总数（在本月具有生育能力）
基于上述逻辑，可以构造如下函数：

function func( n )
{
    if (n == 0 || n == 1) return 1;
    return func(n-1) + func(n-2);
}
func(10);
//89

递归函数的性能问题

递归函数虽然看起来精简又巧妙，但却存在着比较明显的性能问题，为了比较，我们基于第二个例子，再构建一个使用循环语句实现的方法：

function func(n)
{
    var array = [1,1];
    var count = 0;
    var sum = 0;
    if (n === 0 || n ===1) return 1;
    while(count<n-1) {
        array.push(array[count] + array[++count]);
    }
    return array[array.length-1]
}
func(10); //89

很显然上述方法的时间复杂度为n，我们为第二个例子中的递归函数添加一个计数变量：

var count = 0
function func( n )
{
    count++;
    if (n == 0 || n == 1) return 1;
    return func(n-1) + func(n-2);
}
func(10);
count; //177

时间复杂度接近于2n²