當(dāng)一個(gè)函數(shù)在執(zhí)行時(shí)調(diào)用了自身锰什，那么這個(gè)函數(shù)就是遞歸函數(shù)小压。遞歸函數(shù)經(jīng)常用來(lái)解決一些循環(huán)反復(fù)的問(wèn)題壤靶。我們首先列舉一些遞歸函數(shù)的使用場(chǎng)景缚俏。
使用場(chǎng)景
階乘
如果我們要求得 1*2*3*4*5*6 的結(jié)果，可以構(gòu)造一個(gè)如下函數(shù)：
function factorial(n) {
if(n === 1) return 1;
return n*factorial(n-1);
}
factorial(6); //720
斐波拉契數(shù)列
一只兔子贮乳，從出生起第三個(gè)月會(huì)生一只兔子忧换，求第n月的兔子總數(shù)。每個(gè)月的兔子總數(shù)數(shù)列大概是這個(gè)樣子：
1 1 1+1(2) 2+1(3) 3+2(5) 5+3(8) ...
即每個(gè)月兔子的總數(shù)為：
上個(gè)月兔子總數(shù)+上上個(gè)月兔子總數(shù)（在本月具有生育能力）
基于上述邏輯向拆，可以構(gòu)造如下函數(shù)：
function func( n )
{
if (n == 0 || n == 1) return 1;
return func(n-1) + func(n-2);
}
func(10);
//89
遞歸函數(shù)的性能問(wèn)題
遞歸函數(shù)雖然看起來(lái)精簡(jiǎn)又巧妙亚茬，但卻存在著比較明顯的性能問(wèn)題，為了比較浓恳，我們基于第二個(gè)例子刹缝，再構(gòu)建一個(gè)使用循環(huán)語(yǔ)句實(shí)現(xiàn)的方法：
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
很顯然上述方法的時(shí)間復(fù)雜度為n，我們?yōu)榈诙€(gè)例子中的遞歸函數(shù)添加一個(gè)計(jì)數(shù)變量：
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
時(shí)間復(fù)雜度接近于2n2
