[[317905]]

 一.遞歸函數(shù)的理解

1、生活中的遞歸

“遞歸”在生活中的一個(gè)典例就是“問路”。如圖小哥哥進(jìn)入電影院后找不到自己的座位，問身邊的小姐姐“這是第幾排”，小姐姐也不清楚便依次向前詢問，問至第一排的觀眾后依次向后反饋結(jié)果，“我是第一排”，“我是第二排”，···，最終確定自己座位所在排數(shù)。

在這個(gè)過程中充分反應(yīng)了“傳遞”(詢問)和“回歸”(反饋)的思想，故將這種現(xiàn)象稱為“遞歸”。

2、編程中的遞歸

計(jì)算機(jī)有兩個(gè)特點(diǎn)：“很笨”又“很快”。所以將“復(fù)雜問題”轉(zhuǎn)化為“多步驟的簡單問題”后，計(jì)算機(jī)才能高效執(zhí)行。

而遞歸是編程算法的一種，通過調(diào)用自身，將一些復(fù)雜的問題簡單化，便于得出解決方案。

下面通過簡單的案例了解編程中的遞歸

案例：計(jì)算1+2+3+4+5+6的和。

function fn(n){ 
    if(n === 1){ 
        return 1; 
    } 
    return n + fn(n - 1); 
} 
fn(6); 

計(jì)算過程：f(6) = 6 + f(5)

f(6) = 6 + 5 + f(4)

f(6) = 6 + 5 + 4 + f(3)

f(6) = 6 + 5 + 4 + 3 + f(2)

f(6) = 6 + 5 + 4 + 3 + 2 + f(1)

f(6) = 6 + 5 + 4 + 3 + 2 + 1

由上可知遞歸函數(shù)的本質(zhì)：

• 調(diào)用自身

遞歸函數(shù)的實(shí)現(xiàn)有兩個(gè)要素：

1. 終止條件
2. 逐步靠近終止條件

案例中的終止條件是：當(dāng) n === 1 時(shí)，fn(1) === 1。若沒有終止條件，函數(shù)會(huì)繼續(xù)計(jì)算f(0) 、f(-1) 、f(-2) ··· 從而進(jìn)入死循環(huán)，無法得出結(jié)果。

通過計(jì)算過程可以看出，函數(shù)依次計(jì)算f(6)、f(5)、f(4)、f(3)、 f(2)、f(1)，很好的滿足了第二個(gè)要素 逐步靠近終止條件。

二.遞歸函數(shù)的使用

通過以上講解，想必已經(jīng)了解遞歸函數(shù)的原理，

那么遞歸函數(shù)是如何寫出來的呢?

如何利用遞歸函數(shù)解決實(shí)際問題呢?

實(shí)例探索遞歸函數(shù)的書寫“套路”

例題：計(jì)算n的階乘。

步驟 1：找到終止條件，寫給 if

數(shù)學(xué)知識(shí) ：n! = n * (n - 1) * (n - 2) * (n -3) * ··· * 3 * 2 * 1

顯然 終止條件 是 n === 1; 時(shí)， return 1;故可以完成函數(shù)的 前半部分:

function fn(n){ 
    if(n === 1){ 
        return 1; 
    } 
    // 未完待續(xù) 
} 

步驟2：找到函數(shù)的等價(jià)關(guān)系式，寫給 return

數(shù)學(xué)知識(shí) ：n! = n * (n - 1)!

通過數(shù)學(xué)知識(shí) n! = n * (n - 1)! 和遞歸函數(shù)的本質(zhì)(調(diào)用自身)，

可以得出函數(shù)的等價(jià)關(guān)系式為 f(n) = n * f(n - 1);

從而可以完成函數(shù)的后半部分:

function fn(n){ 
    if(n === 1){ 
        return 1; 
    } 
    return n * fn(n - 1); 
} 

至此簡單的遞歸函數(shù)便寫出來了，遞歸函數(shù)最大的特點(diǎn)便是代碼簡潔(簡潔到讓人心虛)。

總結(jié)，遞歸函數(shù)的書寫“套路”

1.找到終止條件，寫給 if

2.找到函數(shù)的等價(jià)關(guān)系式，寫給 return

三.遞歸函數(shù)的問題

想必你會(huì)說，上面的兩個(gè)例題用 循環(huán) 就能輕松寫出來，為何還需要使用遞歸呢?

其實(shí)能用 遞歸 解決的問題，用 循環(huán) 也能解決!而且 遞歸 比 循環(huán) 的運(yùn)算速度要慢，因?yàn)?遞歸 需要逐層調(diào)用函數(shù)，占據(jù)系統(tǒng)內(nèi)存，當(dāng) 遞歸 層級(jí)較深時(shí)，對(duì)性能消耗較大，往往不推薦使用。

問：那遞歸存在的意義是什么?

遞歸 是為了將復(fù)雜問題簡單化，提供解題思路，進(jìn)而得到 “循環(huán)算法”

對(duì)于簡單問題，一眼便能看出“循環(huán)算法”，但對(duì)于抽象問題，通?？梢韵炔扇?遞歸 思想，如：

例題：某人需要走上10級(jí)臺(tái)階，有兩種走法，走法A：一步1個(gè)臺(tái)階;走法B：一步2個(gè)臺(tái)階。兩種走法可以任意交替使用，問走上10級(jí)臺(tái)階共有多少種方法?

這個(gè)問題很難直接看出循環(huán)的解題思路，我們不妨從 遞歸 的角度嘗試解決：

當(dāng)走上第10級(jí)臺(tái)階只差最后一步時(shí)，存在有兩種可能：

第1種：從 第8級(jí) —> 第10級(jí)(一步2個(gè)臺(tái)階)

第2種：從 第9級(jí) —> 第10級(jí)(一步1個(gè)臺(tái)階)

假設(shè)：從 第0級(jí) —> 第8級(jí)，有 x 種走法;

1，1，1，1，1，1，2，2

1，1，1，1，1，2，1，2

1，2，1，1，1，2，2

1，2，1，2，2，2

·······

// 窮舉不盡，共 x 種，每種走法的最后一步都是 2(個(gè)臺(tái)階)

假設(shè)：從 第0級(jí) —> 第9級(jí)，有 y 種走法;

1，1，1，1，1，1，1，2，1

1，1，2，1，1，2，1，1

1，2，1，2，2，1，1

1，2，2，2，2，1

·······

// 窮舉不盡，共 y 種，每種走法的最后一步都是 1(個(gè)臺(tái)階)

那么，從 第0級(jí) —> 第10級(jí)，共有 x + y 種走法。

故，10級(jí)臺(tái)階走法 = 9級(jí)臺(tái)階走法 + 8級(jí)臺(tái)階走法，即 f(10) = f(9) + f(8);

所以我們需要的函數(shù)關(guān)系式是 f(n) = f(n - 1) + f(n - 2);

接下來找 終止條件：

1級(jí)臺(tái)階時(shí)，走法只有1種(1步1臺(tái)階)，是 n === 1; 時(shí)， return 1;

2級(jí)臺(tái)階時(shí)，走法只有2種(2次1步1臺(tái)階 或 1步2臺(tái)階)，是 n === 2; 時(shí)， return 2;

由此可以寫出遞歸函數(shù)

function fn(n){ 
    if(n === 1 || n === 2){ 
        return n; 
    } 
    return fun(n - 1) + fun(n - 2); 
} 

下圖展示了函數(shù)的執(zhí)行過程

可見，在函數(shù)執(zhí)行過程中重復(fù)調(diào)用了多次相同的函數(shù)(相同背景色)，從而極大消耗了系統(tǒng)的性能。經(jīng)過測(cè)試這個(gè) 遞歸函數(shù) 最多可計(jì)算至 f(45);左右的結(jié)果(測(cè)試需謹(jǐn)慎)，這便是 遞歸函數(shù) 存在的主要問題。

那么如何優(yōu)化這個(gè)問題呢?

即，將 遞歸算法改為循環(huán)算法。

通過前面的推導(dǎo)我們知道 f(n) = f(n - 1) + f(n - 2);

1級(jí)臺(tái)階 ==> 走法：1

2級(jí)臺(tái)階 ==> 走法：2

3級(jí)臺(tái)階 ==> 走法：1 + 2 = 3

4級(jí)臺(tái)階 ==> 走法：2 + 3 = 5

5級(jí)臺(tái)階 ==> 走法：3 + 5 = 8

6級(jí)臺(tái)階 ==> 走法：5 + 8 = 13

7級(jí)臺(tái)階 ==> 走法：8 + 13 = 21······

即，只要知道前兩項(xiàng)(1級(jí)臺(tái)階和2級(jí)臺(tái)階)的結(jié)果，就可以自底向上依次推算出后面所有項(xiàng)的結(jié)果。于是便可以寫出 循環(huán)函數(shù)

function fn(n){ 
    if(n === 1 || n === 2){ 
        return n; 
    } 
    var left = 1; // 左邊的數(shù)據(jù) 
    var right = 2; // 右邊的數(shù)據(jù) 
    var sum = 0; 
    for(var i = 3 ; i <= n ; i++){ // 循環(huán)從第3項(xiàng)開始 
        sum = left + right; // 計(jì)算前一次左右數(shù)據(jù)的和 
        left = right; // 把前一次的right賦值給下一次的left 
        right = sum; // 把前一次的和賦值給下一次的right 
    } 
    return sum; 
} 

以上便是通過遞歸思想將抽象問題逐步簡單化，從而得出循環(huán)算法的過程。

循環(huán)算法 解決了 遞歸 消耗系統(tǒng)性能的問題，可以計(jì)算任意數(shù)值。

(當(dāng)數(shù)值太大超出JavaScript數(shù)值范圍時(shí)，返回 Infinity)

四.總結(jié)

1、遞歸結(jié)構(gòu)簡單，易理解，常用于將抽象問題簡單化。

2、遞歸要有終止條件，否則會(huì)變成死遞歸;

3、遞歸算法運(yùn)行效率低、性能消耗大，遞歸深度較大時(shí)慎用(等不到結(jié)果);

4、能用遞歸解決的問題大多都能用循環(huán)解決。