遞歸思想

遞歸指的是一個(gè)過程：函數(shù)不斷引用自身，直到引用的對(duì)象已知。遞歸就是在函數(shù)內(nèi)部調(diào)用自己的函數(shù)被稱之為遞歸。
周末你帶著女朋友去電影院看電影，女朋友問你，咱們現(xiàn)在坐在第幾排?。侩娪霸豪锩嫣诹?，看不清，沒法數(shù)，現(xiàn)在你怎么辦？
遞歸思想：你就問前面一排的人他是第幾排，你想只要在他的數(shù)字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也問他前面的人。就這樣一排一排往前問，直到問到第一排的人，說我在第一排，然后再這樣一排一排再把數(shù)字傳回來。直到你前面的人告訴你他在哪一排，于是你就知道答案了。
這就是一個(gè)非常標(biāo)準(zhǔn)的遞歸求解問題的分解過程，去的過程叫“遞”，回來的過程叫“歸”?；旧?，所有的遞歸問題都可以用遞推公式來表示。
剛剛這個(gè)例子，我們用遞推公式將它表示出來就是這樣的：
f(n) = f(n-1) + 1其中，f(1) = 1
f(n) 表示你想知道自己在哪一排，f(n-1) 表示前面一排所在的排數(shù)，f(1)=1 表示第一排的人知道自己在第一排。

遞歸的三個(gè)條件

剛剛這個(gè)例子是非常典型的遞歸，那究竟什么樣的問題可以用遞歸來解決呢？我總結(jié)了三個(gè)條件，只要同時(shí)滿足以下三個(gè)條件，就可以用遞歸來解決。

• 一個(gè)問題的解可以分解為幾個(gè)子問題的解
  何為子問題？子問題就是數(shù)據(jù)規(guī)模更小的問題。比如，前面講的電影院的例子，你要知道，“自己在哪一排”的問題，可以分解為“前一排的人在哪一排”這樣一個(gè)子問題。
• 這個(gè)問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
  比如電影院那個(gè)例子，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一樣的。
• 存在遞歸終止條件
  把問題分解為子問題，把子問題再分解為子子問題，一層一層分解下去，不能存在無限循環(huán)，這就需要有終止條件。
  還是電影院的例子，第一排的人不需要再繼續(xù)詢問任何人，就知道自己在哪一排，也就是 f(1)=1，這就是遞歸的終止條件。

編寫遞歸案例

假如這里有 n 個(gè)臺(tái)階，每次你可以跨 1 個(gè)臺(tái)階或者 2 個(gè)臺(tái)階，請問走這 n 個(gè)臺(tái)階有多少種走法？如果有 7 個(gè)臺(tái)階，你可以 2，2，2，1 這樣子上去，也可以 1，2，1，1，2 這樣子上去，總之走法有很多，那如何用編程求得總共有多少種走法呢？
我們仔細(xì)想下，實(shí)際上，可以根據(jù)第一步的走法把所有走法分為兩類，第一類是第一步走了 1 個(gè)臺(tái)階，另一類是第一步走了 2 個(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)

有了遞推公式，遞歸代碼基本上就完成了一半。我們再來看下終止條件。當(dāng)有一個(gè)臺(tái)階時(shí)，我們不需要再繼續(xù)遞歸，就只有一種走法。所以 f(1)=1。這個(gè)遞歸終止條件足夠嗎？我們可以用 n=2，n=3 這樣比較小的數(shù)試驗(yàn)一下。
n=2 時(shí)，f(2)=f(1)+f(0)。如果遞歸終止條件只有一個(gè) f(1)=1，那 f(2) 就無法求解了。所以除了 f(1)=1 這一個(gè)遞歸終止條件外，還要有 f(0)=1，表示走 0 個(gè)臺(tái)階有一種走法，不過這樣子看起來就不符合正常的邏輯思維了。所以，我們可以把 f(2)=2 作為一種終止條件，表示走 2 個(gè)臺(tái)階，有兩種走法，一步走完或者分兩步來走。
所以，遞歸終止條件就是 f(1)=1，f(2)=2。這個(gè)時(shí)候，你可以再拿 n=3，n=4 來驗(yàn)證一下，這個(gè)終止條件是否足夠并且正確。
我們把遞歸終止條件和剛剛得到的遞推公式放到一起就是這樣的：

f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)

有了這個(gè)公式，我們轉(zhuǎn)化成遞歸代碼就簡單多了。最終的遞歸代碼是這樣的：

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

總結(jié)：

• 一、什么是遞歸？
  1.遞歸是一種非常高效、簡潔的編碼技巧，一種應(yīng)用非常廣泛的算法，比如DFS深度優(yōu)先搜索、前中后序二叉樹遍歷等都是使用遞歸。
  2.方法或函數(shù)調(diào)用自身的方式稱為遞歸調(diào)用，調(diào)用稱為遞，返回稱為歸。
  3.基本上，所有的遞歸問題都可以用遞推公式來表示，比如
  f(n) = f(n-1) + 1;
  f(n) = f(n-1) + f(n-2);
  f(n)=n*f(n-1);
• 二、為什么使用遞歸？遞歸的優(yōu)缺點(diǎn)？
  1.優(yōu)點(diǎn)：代碼的表達(dá)力很強(qiáng)，寫起來簡潔。
  2.缺點(diǎn)：空間復(fù)雜度高、有堆棧溢出風(fēng)險(xiǎn)、存在重復(fù)計(jì)算、過多的函數(shù)調(diào)用會(huì)耗時(shí)較多等問題。
• 三、什么樣的問題可以用遞歸解決呢？
  一個(gè)問題只要同時(shí)滿足以下3個(gè)條件，就可以用遞歸來解決：
  1.問題的解可以分解為幾個(gè)子問題的解。何為子問題？就是數(shù)據(jù)規(guī)模更小的問題。
  2.問題與子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
  3.存在遞歸終止條件
• 四、如何實(shí)現(xiàn)遞歸？
  1.遞歸代碼編寫
  寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼。
  2.遞歸代碼理解
  對(duì)于遞歸代碼，若試圖想清楚整個(gè)遞和歸的過程，實(shí)際上是進(jìn)入了一個(gè)思維誤區(qū)。
  那該如何理解遞歸代碼呢？如果一個(gè)問題A可以分解為若干個(gè)子問題B、C、D，你可以假設(shè)子問題B、C、D已經(jīng)解決。而且，你只需要思考問題A與子問題B、C、D兩層之間的關(guān)系即可，不需要一層層往下思考子問題與子子問題，子子問題與子子子問題之間的關(guān)系。屏蔽掉遞歸細(xì)節(jié)，這樣子理解起來就簡單多了。
  因此，理解遞歸代碼，就把它抽象成一個(gè)遞推公式，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去分解遞歸的每個(gè)步驟。
• 五、遞歸常見問題及解決方案
  1.警惕堆棧溢出：可以聲明一個(gè)全局變量來控制遞歸的深度，從而避免堆棧溢出。
  2.警惕重復(fù)計(jì)算：通過某種數(shù)據(jù)結(jié)構(gòu)來保存已經(jīng)求解過的值，從而避免重復(fù)計(jì)算。
• 六、如何將遞歸改寫為非遞歸代碼？
  籠統(tǒng)的講，所有的遞歸代碼都可以改寫為迭代循環(huán)的非遞歸寫法。如何做？抽象出遞推公式、初始值和邊界條件，然后用迭代循環(huán)實(shí)現(xiàn)。
  參考如何用三行代碼找到“最終推薦人

實(shí)例

實(shí)例

• 階乘

def fact(n):

    if n==1:

        return 1

    return n * fact(n -1)

上面就是一個(gè)實(shí)現(xiàn)階乘的遞歸函數(shù)，我們來試一試。

>>> fact(1)
1
>>> fact(5)
120

可能有點(diǎn)懵吧，來看一看計(jì)算過程吧：

===> fact(5)

===> 5 * fact(4)

===> 5 * (4 * fact(3))

===> 5 * (4 * (3 * fact(2)))

===> 5 * (4 * (3 * (2 * fact(1))))

===> 5 * (4 * (3 * (2 * 1)))

===> 5 * (4 * (3 * 2))

===> 5 * (4 * 6)

===> 5 * 24

===> 120

• 斐波那契數(shù)列

def fib(n):
    if n <2:
         return n
    else:
        return fib(n -1) + fib(n -2)

• 漢諾塔

def hanoti(n,x1,x2,x3):
    if(n == 1):
        print('move:',x1,'-->',x3)
        return
    hanoti(n-1,x1,x3,x2)
    print('move:',x1,'-->',x3)
    hanoti(n-1,x2,x1,x3)