遞歸是一種高效、簡(jiǎn)潔的編碼技巧

滿足下面三點(diǎn)的問題，即可用遞歸來解決

1. 一個(gè)問題的解可以分解為幾個(gè)子問題的解
2. 這個(gè)問題與分解后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
3. 存在遞歸終止條件

如何編寫遞歸代碼

寫出遞推公式，找出終止條件，翻譯成遞歸代碼

遞歸代碼的問題

• 有堆棧溢出風(fēng)險(xiǎn)
• 重復(fù)計(jì)算
• 函數(shù)調(diào)用耗時(shí)多
• 空間復(fù)雜度高

函數(shù)調(diào)用會(huì)使用棧來保存臨時(shí)變量。每調(diào)用一個(gè)函數(shù)，都會(huì)將臨時(shí)變量封裝為棧幀壓入內(nèi)存棧，等函數(shù)執(zhí)行完成返回時(shí)，才出棧。系統(tǒng)?；蛱摂M機(jī)?？臻g一般都不大，如果遞歸求解的數(shù)據(jù)規(guī)模很大，調(diào)用層次很深，一直壓入棧，就會(huì)有堆棧溢出的風(fēng)險(xiǎn)。

問題舉例

1. 假如這里有 n 個(gè)臺(tái)階，每次你可以跨 1 個(gè)臺(tái)階或者 2 個(gè)臺(tái)階，請(qǐng)問走這 n 個(gè)臺(tái)階有多少種走法？

   思路：根據(jù)第一步的走法把所有走法分為兩類，第一類是第一步走了一個(gè)臺(tái)階，第二類是第一步走了兩個(gè)臺(tái)階，所以n個(gè)臺(tái)階的走法就等于先走1階后，n-1個(gè)臺(tái)階的走法 加上 先走2階后，n-2個(gè)臺(tái)階的走法。
   所以遞推公式就是：f(n) = f(n-1) + f(n-2)
   終止條件就是：f(1) = 1; f(2) = 2

   代碼：

/**
 * 帶有重復(fù)計(jì)算
 * @param $n
 * @return int
 */
function f($n)
{
    if ($n == 1) return 1;
    if ($n == 2) return 2;
    return f($n-1) + f($n-2);
}


// ===========


$hasSolved = [];

/**
 * 去除重復(fù)計(jì)算
 * @param $n
 * @param $hasSolved
 * @return int
 */
function f($n)
{
    if ($n == 1) return 1;
    if ($n == 2) return 2;

    global $hasSolved;

    if (isset($hasSolved[$n])) {
        return $hasSolved[$n];
    }

    $result = f($n-1) + f($n-2);
    $hasSolved[$n] = $result;
    return $result;
}


// ===========


/**
 * 非遞歸 （相當(dāng)于 斐波那契數(shù)列求和）
 * $pre -> f(n-1), $prepre -> f(n-2)
 * @param $n
 * @return int
 */
function f($n)
{
    if ($n == 1) return 1;
    if ($n == 2) return 2;

    $result = 0;
    $pre = 2;
    $prepre = 1;

    for ($i = 3; $i < $n; $i++) {
        $result = $pre + $prepre;
        $prepre = $pre;
        $pre = $result;
    }
    
    return $result;
}