前言

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

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

正文

一、入門的階乘

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

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

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

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

二、難度進(jìn)階

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

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

因為本篇章的主角是遞歸，所以咱們依舊用遞歸的思路去解題。咱先來思考一下，這題是不是比階乘難？答案是肯定的。

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

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

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

1、找終止條件

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

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

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

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

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

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

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

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

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

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

image.png

我著重圈了兩個地方：

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

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

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

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

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

這一步其實就是解釋了，遞的過程為什么不要鉆牛角尖，去基于當(dāng)前去想到底有多少種走法。因為一旦想要知道答案，就要展開所有可能。

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

解題代碼

所以這個題目的代碼就很簡單了：

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

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

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

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

1、避免堆棧溢出

這一點還是比較好理解的，因為一旦終止條件有問題，那么無限遞歸就會造成棧溢出。

Exception in thread "main" java.lang.StackOverflowError

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

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

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

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

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

這里有一個非遞歸的實現(xiàn)，同樣也來自 極客時間《數(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;
}

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

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

尾聲

唉...自己是真的菜。

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