前言

最近跨界了解了一下后端的知識(shí)，對(duì)數(shù)據(jù)庫(kù)加索引可以帶來顯著提速的現(xiàn)象感到很神奇（原諒我如此的土鱉）?？丛硎怯玫搅薆+數(shù)這個(gè)數(shù)據(jù)結(jié)構(gòu)...所以出來混都是要還的。

鑒于欠的知識(shí)比較多，一步步來，這次的主題是遞歸。沒辦法畢竟自己太菜，得一點(diǎn)點(diǎn)補(bǔ)。

正文

一、入門的階乘

提到遞歸，我猜大多數(shù)同學(xué)第一印象就是：f(n) = f(n-1) * n 階乘。所以咱們今天就先從最基礎(chǔ)的階乘來入手。

階乘是一個(gè)非常線性的問題。用我們的大腦來構(gòu)建調(diào)用棧也很容易和清晰。函數(shù)調(diào)用單項(xiàng)的一層層遞下去，然后通過最終的return條件，再一層層的return回去（歸）。

遞歸實(shí)現(xiàn)的階乘很好理解，那咱們就趁熱打鐵總結(jié)一下遞歸的特點(diǎn)：

• 1. 一個(gè)問題的解可以分解為多個(gè)相同類型子問題
  • 咱們階乘中f(n-1) * n就是抽象出來的子問題。而且無論存在多少種入?yún)⒌那闆r，子問題解題思路是一致的。
• 2. 存在遞歸終止條件
  • 子問題可能有很多，如果無限重復(fù)下去，那么就是棧溢出了，所以需要有終止條件。

二、難度進(jìn)階

有了階乘的入門，咱們來稍稍提升一些難度：假如這里有 n 個(gè)臺(tái)階，每次你可以跨 1 個(gè)臺(tái)階或者 2 個(gè)臺(tái)階，請(qǐng)問走這 n 個(gè)臺(tái)階有多少種走法？

PS：當(dāng)年我看到這個(gè)題目是非常蒙蔽的，每一步都有兩種選擇，很難搞哇。

因?yàn)楸酒碌闹鹘鞘沁f歸，所以咱們依舊用遞歸的思路去解題。咱先來思考一下，這題是不是比階乘難？答案是肯定的。

那它比階乘難在哪呢？難在它不再是線性的問題！ 每一步都有兩個(gè)不同的選擇。

咱不管這么多，先套遞歸的特點(diǎn)：1、找子問題，構(gòu)建合適的遞歸公式；2、找到合適的終止條件。

很多教程都是先找子問題構(gòu)建遞歸公式，但是這次咱們反過來先找終止條件 。

1、找終止條件

既然是找終止條件，那咱們就得明確題目中的終止是啥，就是走完臺(tái)階，最終走完臺(tái)階的方式只有兩種：要么是跨 1 個(gè)臺(tái)階走完，要么是跨 2 個(gè)臺(tái)階走完。

好，那咱們的終止條件其實(shí)就出來了，假設(shè)n表示當(dāng)前還剩多少階臺(tái)階，返回值表示有幾種走法：

• if(n = 1) return 1；此時(shí)只有一種走法；
• if(n = 2) return 2；此時(shí)有兩種走法。

咱們找到了終止條件，這里停下來咱們想一個(gè)問題：咱們終止條件找的是如果只剩1個(gè) / 2個(gè)臺(tái)階時(shí)的走法。

那么我們把1/2這兩個(gè)實(shí)際的參數(shù)抽象一下，是不是可以轉(zhuǎn)化為我們?cè)僬?code>n - 1個(gè)臺(tái)階的走法和n - 2個(gè)臺(tái)階的走法。(如果此時(shí)n = 3，就得到了我們終止條件的答案)

2、構(gòu)建合適的遞歸公式

通過上邊找終止條件的過程，抽象一下就會(huì)發(fā)現(xiàn)：我們本質(zhì)就是在尋找n - 1個(gè)臺(tái)階的走法和n - 2個(gè)臺(tái)階的走法一共有多少種。

所以子問題就出來了：基于當(dāng)前臺(tái)階數(shù)，走一階有多少種走法 + 走兩階有多少種走法。（換成偽碼就是f(n) = f(n-1)+f(n-2)）

注意（這句話一定要看） ：這里千萬不要陷進(jìn)去，也就是不要基于當(dāng)前去思考：有多少種走法！ 因?yàn)?strong>這不是當(dāng)前子問題該考慮的事情，這個(gè)問題的答案會(huì)在歸的過程由前一個(gè)子問題回答 。

如果非要思考，也沒關(guān)系。我貼張圖幫助你去思考：

image.png

我著重圈了兩個(gè)地方：

一個(gè)是不滿足終止條件“遞的過程”

該行為會(huì)按照我們的遞歸公式，逐步遞出全部可能性，也就是為什么想告知大家不要陷進(jìn)去。

對(duì)于咱們這個(gè)問題，如果想要展開遞的過程，那么就會(huì)像二叉樹一樣不斷延展開來，然而這個(gè)展開的過程對(duì)于我們來說沒有任何意義，因?yàn)檫@本身就是重復(fù)的過程，這種事不應(yīng)該是我們?nèi)四X該做的。

另一個(gè)是滿足終止條件“歸的過程”

歸的過程說白了就是：某一層子問題找到了答案，逐層往上告知的過程。

這一步其實(shí)就是解釋了，遞的過程為什么不要鉆牛角尖，去基于當(dāng)前去想到底有多少種走法。因?yàn)橐坏┫胍来鸢?，就要展開所有可能。

然而我們的每一層的答案都會(huì)由下一層子問題在歸的過程中解答。

解題代碼

所以這個(gè)題目的代碼就很簡(jiǎn)單了：

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

三、遞歸的優(yōu)缺點(diǎn)

硬說遞歸的有點(diǎn)，個(gè)人感覺那就是代碼量少...但是同樣也是它的缺點(diǎn)，代碼越簡(jiǎn)單理解成本就越高。當(dāng)然這個(gè)問題不痛不癢。

這一Part咱們主要說一下遞歸比較關(guān)鍵兩個(gè)問題：

1、避免堆棧溢出

這一點(diǎn)還是比較好理解的，因?yàn)橐坏┙K止條件有問題，那么無限遞歸就會(huì)造成棧溢出。

Exception in thread "main" java.lang.StackOverflowError

2、重復(fù)執(zhí)行

這個(gè)問題算是遞歸中比較重點(diǎn)的缺點(diǎn)。借助下面這張圖，我圈起來的f(4)、f(3)，很明顯看到它們被重復(fù)執(zhí)行了很多遍。

圖片來自于：極客時(shí)間《數(shù)據(jù)結(jié)構(gòu)于算法之美》

當(dāng)然解決起來也很簡(jiǎn)單，那就是加緩存。每次執(zhí)行的時(shí)候先去緩存里讀，沒有的話再執(zhí)行遞的過程。

四、非遞歸實(shí)現(xiàn)

這里有一個(gè)非遞歸的實(shí)現(xiàn)，同樣也來自 極客時(shí)間《數(shù)據(jù)結(jié)構(gòu)于算法之美》。代碼是這樣的：

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  
  int ret = 0;
  int pre = 2;
  int prepre = 1;
  for (int i = 3; i <= n; ++i) {
    ret = pre + prepre;
    prepre = pre;
    pre = ret;
  }
  return ret;
}

這代碼比較巧妙，篇幅有限就不具體展開。

這里留個(gè)引子供大家結(jié)合思考：把這段代碼和上邊那張重復(fù)執(zhí)行的圖，結(jié)合在一起思考。

尾聲

唉...自己是真的菜。

最后推薦一下極客時(shí)間《數(shù)據(jù)結(jié)構(gòu)于算法之美》，有興趣的同學(xué)可以用掃碼購(gòu)買。