遞歸是一種高效、簡(jiǎn)潔的編碼技巧
滿足下面三點(diǎn)的問題僻爽，即可用遞歸來解決
- 一個(gè)問題的解可以分解為幾個(gè)子問題的解
- 這個(gè)問題與分解后的子問題头遭，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
- 存在遞歸終止條件
如何編寫遞歸代碼
寫出遞推公式苞俘，找出終止條件盹沈，翻譯成遞歸代碼
遞歸代碼的問題
- 有堆棧溢出風(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)椝嗤恚或虛擬機(jī)棧空間一般都不大仔戈，如果遞歸求解的數(shù)據(jù)規(guī)模很大关串，調(diào)用層次很深，一直壓入棧监徘，就會(huì)有堆棧溢出的風(fēng)險(xiǎn)晋修。
問題舉例
-
假如這里有 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;
}
