[算法系列] 深入遞歸本質+經典例題解析——如何逐步生成, 以此類推,步步為營

本文是遞歸系列的第三篇, 第一篇介紹了遞歸的形式以及遞歸設計方法(迭代改遞歸),;第二篇以遞歸為引子, 詳細介紹了快排和歸排以及堆排的核心思想; 本篇主要通過幾個題, 從遞推, 歸納法的角度, 深入了介紹了遞歸的本質和具體應用.

往期回顧:

搞懂遞歸, 看這篇就夠了 !! 遞歸設計思路 + 經典例題層層遞進

遞歸應用: 快速排序+歸并排序算法及其核心思想與拓展 … 附贈 堆排序算法

回顧我們在第一篇文章討論的遞歸中, 下面是我們能夠看到現象形式:

f(n) -> f(n - 1) -> f(n-2) -> ... -> f(1)

但實際本質是: 為了解決/完成 f(n), 必先完成f(n- 1); 為解決f(n-1),必先解決f(n-2) … 那么最先要解決f(1)

f(1) -> f(2) -> f(3) -> ... ->f(n)

回顧以前學過的數學歸納法:

1. 證明當k=1時,條件成立 2. 假設k=n(n>=1)時,條件成立 3. 證明k=n+1,條件成立 得到結論: k取任意正整數時,條件成立

如果沒記錯的話這叫第一數學歸納法, 往往我們用來證明構造的某些式子在給定自然數集合(全體或局部)的正確性. 而數學歸納法本質是什么呢? 通俗來看, 就是首先證明了k=1時的正確性, 然后證明k = n 成立可以推導出k=n+1成立. 根據上述兩個條件可以得出k=2也就成立了… 然后k=3也就成立… 本質是遞推.

• 遞歸解決的本質是先從f(1)->f(2)->…->f(n), 小問題解決了,再解決大問題
• 數學歸納法式從k = 1 逐層證明, 或者說證明k=n和k=n+1的關系,然后遞推
• 遞推, 就是按照前一個(或幾個)的關系推理出下一個 …

recursion一詞既可以翻譯為遞推,也可以翻譯為遞歸, 這里的歸應該是是規約的意思. 注意這里的遞歸和編程形式中的 遞歸調用 是有點區別的, 編程中談到的形式化更多一些, 而數學本質還是和遞歸遞推沒有區別.

遞歸, 遞推, 數學歸納法本質正是同一種東西.

好了,現在看來知道了這些似乎作用不大. 我們還是舉個例子, 搞懂遞歸, 看這篇就夠了 !! 遞歸設計思路 + 經典例題層層遞進 中的青蛙上樓梯問題.

1. 再談青蛙上樓梯

樓梯有n個臺階, 一個青蛙一次可以上1 , 2 或3 階 , 實現一個方法, 計算該青蛙有多少種上完樓梯的方法

文中給出了遞歸的解法:

(回憶找重復,找變化,找出口)

假如青蛙上10 階, 那么其實相當于要么 站在第9 階向上走1步,要么 站在第8 階向上走兩步, 要么在第7階向上走3步. 每個大于3階樓梯的問題都可以看成幾個子問題的堆疊

變化:令f(n) 為 青蛙上n階的方法數. 則f(n) = f(n -1) +f(n - 2) + f(n -3) , 當n >= 3

出口: 當n = 0 時 ,青蛙不動 , f(0) = 0; n = 1時 ,有1種方法 , n = 2 時 有2 種方法

def f(n):if n == 0 :return 1 #站著不動也得返回1的, 因為實際上0種方法的是沒意義if n == 1:return 1if n == 2:return 2return f(n - 1) +f(n - 2) +f(n -3)

顯然這樣的遞歸方法不是很直觀的, 其實一開始拿到這題 , 普通地想, 應該是拿出張白紙來, 左邊起名一列: 階數 , 右邊起名一列: 走法

階數 走法 1 1 0->1 2 2 0->1->2 0->2 3 4 0->1->2->3 0->1->3 0->2->3 0->3 4 7 ... ... ...

詳細康康階數為4時的走法:

注意我分成了三列寫, 如果不看紅色部分的話, 三列分別代表了上第1,2,3階的方法. 現在帶著紅色的 ->4 一起看:

• 第一列: 相當于先上到第1階再一次上到4 (因為最大可以跨3階嘛)
• 第二列: 相當于先上到第2階再一次上到4 (相當于最后一次跨2階嘛)
• 第三列:相當于先上到第3階再一次上到4(最后一次跨1階即可)

顯然上到第四階的方法剛好就是這三列的和了 …

到這里, 有興趣的同學可以在寫出階數為5的走法. 但其實也會得到下面的結論:

• 第一列: 相當于先上到第2階再一次上到5 (因為最大可以跨3階嘛)
• 第二列: 相當于先上到第3階再一次上到5 (相當于最后一次跨2階嘛)
• 第三列:相當于先上到第4階再一次上到5(最后一次跨1階即可)

顯然上到第五階的方法剛好就是這三列的和了 …

…想一想, 規律也就可以得出了

階數為n的走法. 但其實也會得到下面的結論:

• 或者先上到第n-3階再一次上到n (因為最大可以跨3階嘛)
• 或者先上到第n-2階再一次上到n (相當于最后一次跨2階嘛)
• 或者于先上到第n-1階再一次上到n(最后一次跨1階即可)

所以 f(n) = f(n -1) +f(n - 2) + f(n -3) 不是憑空產生, 而真是一步一步的像上面一樣推出來 – 遞歸表達也是如此

下面就可以自然的得到遞歸法實現了

def go_stairs(n):if n <= 1:return 1if n == 2 :return 2if n == 3 :return 4return go_stairs(n - 1) + go_stairs(n - 2) + go_stairs(n - 3)

寫出了出口條件, 寫出了遞推式, 計算機不就幫我們像上面一樣, 一步一步地推下去了么…

同樣的, 我們也可以按照我們的推理演算的順序, 用一個長度為3的數組, 保存每次得到的f(n -1) ,f(n - 2) ,f(n -3), 下一輪再更新…這就是我們遞推的迭代法實現 :

def go_stairs_ite(n):#聲明一個長度為4的數組保存每次計算得到值, 用于存儲每次計算所需的三個值和一個結果值arr =[]if n <= 1:return 1if n == 2 :return 2if n == 3 :return 4arr[0] = 1arr[1] = 2arr[2] = 4 #1 2 4 ()for i in range(4, n+1):arr[3] = arr[0] #1 2 4 1 不斷地空出來一個固定位置,存結果 arr[0] = arr[1] #2 2 4 1 arr[1] = arr[2] #2 3 4 1arr[2] = arr[3] + arr[0] + arr[1] #2 4 7 1return arr[2]

2. 機器人走方格 cc150 9.2

有一個 X*Y 的方格, 一個機器人只能走格點且只能向右或者向右走, 要從左上角走到左下角 請設計一個算法, 計算機器人有多少種走法 給定兩個個正整數X , Y, 返回機器人走法的數目.

分析如下:

得到遞推公式和出口條件就可以寫出遞歸形式代碼:

''' 遞歸形式 ''' def robot_go_grim(x, y):if (x == 1 or y == 1):return 1return robot_go_grim(x - 1 , y ) +robot_go_grim(x , y - 1 )

想清楚了, 代碼看上去是不是異常簡潔呢?

現在考慮迭代形式: 我們知道,

• 如果只有一個格子, 那么終點即為起點, 結果為1
• n * 1 或 1 * m 的情況, 總是只有一種走法

在對應格子中填上從此處到右下角的走法, 目前可得到:

然后就可以填格子, 根據就是f(n,m) = f(n - 1,m) +f(n, m -1) .

這其實也就相當于:當前的方法數 = 自己下方格子處的方法數 + 右邊格子處的方法數

• 填到圖中值為6 的格子處, 也就得到了f(3,3)的解
• 填到圖中值為5 的格子處, 也就得到了f(2,5)的解

''' 迭代形式 ''' def robot_go_grim_ite(x,y):dp = [[0 for i in range(0, y)] for j in range(0, x)]#出口條件(邊界條件)for j in range(0 , y):dp[x - 1][j] = 1for i in range(0, x):dp[i][y - 1] = 1# print_matrix(dp)for i in range(x - 2 , -1 , -1):for j in range(y - 2 , -1 , -1):dp[i][j] = dp[i +1] [j] + dp[i][j +1]return dp[0][0]

3.輸出合法括號cc9.6

編寫一個方法,打印n對括號的全部有效組合(即左右括號正確匹配) 示例 輸入:3 輸出:()()(),((())),(())(),()(()),(()())

按照前兩道的思路, 我們依然從最初開始逐步遞推: 尋找每次大規模問題和其小一號問題的關系. 同時出口條件又是已知的

def proper_bracket(n):''':param n: 輸入括號對數:return:'''#聲明一個set用于存放結果sn = set()#出口條件if n == 1 :sn.add("()")return snsn_1 = proper_bracket(n-1) #聲明小一號規模的子問題,上一次求得的sn作為下一次的sn_1for e in sn_1: #以下全是歸回來的副作用, 闡明子問題與父問題的關系sn.add("()"+e) sn.add(e+"()")sn.add("("+e+")")return snprint(proper_bracket(3))

稍微解釋下上述代碼,

• n=1時為出口條件,答案明確
• n>1時依次調用n-1, 因此首先求得的是n=2時, sn_1="()",針對它的每一項進行加左,加右,加外三個操作得到sn, 再逐次返回

下面的迭代形式正是遞推過程的正向體現

''' 迭代形式 ''' def proper_bracket_ite(n):sn = set()sn.add("()")if n ==1 :return snfor i in range(2 , n+1 ):sn_new = set() #從n=2開始每次創建一個新集合set_new, 從sn推出set_newfor e in sn:sn_new.add("()" +e)sn_new.add(e + "()")sn_new.add("(" + e + ")")sn = sn_new #set_new變sn,周而復始return sn

4.集合的所有子集cc9.4

編寫一個方法,返回int集合的所有子集 # 例如: # 輸入: [1,2,3] # 輸出: [],[1],[1,2],[1,2,3],[2,3],[3],[1,3],[2]

此題我們同樣按照小規模往大規模進行推理,

• 當只有一個元素時, 只用考慮有這個元素(子集1),或者沒有這個元素(子集2),

• 當有兩個元素時,可以這樣考慮:

  • 加入第一個元素 =>形成子集1
  • 加入第二個元素=>形成子集2
  • 彈出第二個元素
  • 彈出第一個元素
  • 加入第二個元素=>形成子集3

• 當有多個元素時, 對于每個元素,都有試探放入或者不放人集合中兩個選擇:

  • 選擇該元素放入,遞歸地進行后續元素的選擇,完成放入該元素后續所有元素的試探;

  • 之后將其拿出

  • 再進行一次選擇不放入該元素,遞歸地進行后續元素的選擇,完成不放入該元素時對后續元素的試探

設arr傳入的數組, item為每一個子集, res為最終的結果集, i 表示當前arr的下標

下圖演示遞歸求解的調用思路:

代碼如下

def get_subset(arr):item = list()res = list(list())generate(0 , arr, item, res)print(res)def generate(i , arr , item, res):''':param i: 表示當前操作的arr下標:param arr: 初始傳入的int集合:param item: 存放每個子集的set:param res: 存放最終結果的set:return:'''if(i >= len(arr)):returnitem.append(arr[i])temp_item=list(item) #這里不能直接res.append(item),否則下一次更新res中的item會跟著變化,這里只需要其元素res.append(temp_item)#重點generate(i +1, arr, item ,res)item.pop() #將當前元素拿出generate(i + 1, arr, item ,res) #遞歸調用不考慮當前元素的情況

對于這種放或不放的01事件，還可以用二進制表示的方法。。具體來看，就是就是是和否可能性的組合問題.以原始集合{1,2,3}為例,下圖可以很好的表示子集的所有可能性:

因此,我們可以用當前位置上1或0表示選或不選當前位置上的元素, 數組長度即為二進制數的位數, 即可用一個3位二進制數保存{A,B.C}的所有可能性.

而在尋找這種可能時, 可從0遍歷到2^(len(arr))-1, 其中的每一個二進制數,剛好表達的是一種可能性. 比如:110,即為{A,B}.

def get_subset_ite(arr):res= list() #最終結果集for i in range(2**len(arr) - 1 ,-1 , - 1):item = list() #d當前子集for j in range(len(arr) - 1 , -1 ,- 1): #j是遍歷每一位,當該為為1,則對應的元素加入if (i>>j) & 1 == 1: #若該二進制位為1,則加入itemitem.append(arr[j])res.append(item) return(res)

5.全排列cc9.5

寫一個方法,返回一個字符串數組的全排列 例如 輸入:"ABC" 返回:"ABC","ACB","BAC","BCA","CAB","CBA"

這個問題和剛剛的那個子集問題結合起來看

• 子集問題是:針對某一位上的元素,選還是不選這個元素的問題(0或1). 對每一位來說均有兩種可能, 總計為2^n個情況(子集)
• 全排列問題是: 每個位置都要選,但是是選n個當中哪一個的問題. 其次,當前選定一個了,下一個可選情況就少1了.因此情況個數為n!

那么如何用遞歸思考方式著手解決呢? 還從小規模逐漸推吧

當串長度為1時:“a”, 只有一種情況

當串長度為2時,比如"ab": 初始"a", 加一個"b":

• “b"可以放在"a"的前面形成"ab”
• 也可以放在"a"后面形成"ba"

當串長度為3時,“ab"或"ba”, 加一個"c":

• 對于"ab",有a左,ab中間,b右三個位置可加入, 分別形成三個串
• 對于"ba",同樣有三個為加如c,同樣形成三個新串

由此推而廣之到n時:

令 S(n-1) = {前n-1的子串全排列集合}, 則S(n)與S(n-1)關系為:for each item in S(n-1):for each empty between str[i] and str[i+1]:item.append(str[n])res.append(item)

上面的方法, 其實并不是我們平時所一下想到的, 那么我們平時是怎么想的呢?

• 先以a開頭, b開頭 , c開頭寫…abcd
• 調換最后兩位順序…
• 逐漸從后面向前面調換順序, 寫完所有a打頭的item
• 接下來交換a和b, 以b打頭, a第二個寫… 寫完為止
• 然后依然b打頭, c第二個寫…
• 接下來交換a和c,c打頭,a第二個…

看文字感覺不好表述, 那么還是看圖好了:

藍色數字為調用回溯順序

代碼:

res = list() #全局: 最終結果list def get_all_array(str):arr = list(str)arr.sort() #先排好序generate(arr, 0)return resdef generate(arr ,k ):#遞歸走到底了 表示排好了if k == len(arr):item = "".join(arr)res.append(item)#從第k位開始的每個字符都嘗試放在新排列的第k個位置for i in range(k , len(arr)):swap(arr , k ,i) #交換, 形成新的順序, 比如 bc=>cbgenerate(arr , k+1) #遞歸調用swap(arr , k ,i) #這是返回時的副作用, 再次交換, 復原 == >回溯# 輔助函數swap def swap(arr , i ,j):if i <0 or j < 0 or i > len(arr) or j > len(arr):return "i or j is out of indedx"tem = arr[i]arr[i] = arr[j]arr[j] = tem ['abc', 'acb', 'bac', 'bca', 'cba', 'cab']

上面這個交換-回溯法很簡潔, 但是并不能按照字典序打印, 下面這個方法就可以將其字典序打印了

偽代碼如下:

res = list() #存放最終結果 generate("" , str) #初始時前綴為空generate(prefix, str) :if prefix.length == str.length:res.add(prefix) #結果集中放入prefixreturnfor each ch in str:# 這個字符可用: 在pre中出現的次數 < 在字符集中出現的次數 (這是關鍵)if prefix.count(ch) < str.count(ch)generate(prefix + ch ,str) #將ch加入prefix中,繼續遞歸調用

好了, 本次介紹就到這里, 下面來小結一下:

• 本文是遞歸系列的第三篇, 第一篇介紹了遞歸的形式以及遞歸設計方法(迭代改遞歸),;第二篇以遞歸為引子, 詳細介紹了快排和歸排以及堆排的核心思想; 本篇主要通過幾個題, 從遞推, 歸納法的角度, 深入了介紹了遞歸的本質和具體應用.

• 本文所談遞歸的"本質"，是數學角度上的，且并未繼續深入（比如所謂的封閉式計算方法，直接求通項等). 同時,關于計算機中的遞歸(比如棧開辟,函數存儲等問題)并未涉及, 待以后補充學習后一定補上.

• 前兩個題是數值類問題, 后三個題為非數值型問題. 他們的核心在這里都是: 逐步生成, 以此類推 .

• 遞歸設計的方法依然還是 搞懂遞歸, 看這篇就夠了 !! 遞歸設計思路 + 經典例題層層遞進 中詳細介紹的:

  • 找出口條件 ==> 邊界, 最小規模的問題 ==> 初始情況
  • 找不變 ==> 解決問題的方法不應變化, f(n) 與 f(n-m) 才能表述成父問題與子問題的關系(回憶前面的漢諾塔問題)
  • 找變化 ==> n規模的問題與n-m規模問題之間的關系(考慮走格子, 全排列問題) ==> 遞推公式中的n

• 本篇介紹的一些東西將在后續對回溯, dfs ,動態規劃的介紹中有所體現. 這里主要強調的是:

  如何觀察問題 ==> 從小規模開始遞推 ==> 找出本質(遞推公式) ==> 按照方法,設計算法(遞歸, 迭代)

接下來的文章將對遞歸的一些應用: dfs, dp等進行介紹
下一篇:[算法系列] 搞懂DFS——設計思路+經典例題(數獨游戲, 部分和, 水洼數目)圖文詳解

總結

以上是生活随笔為你收集整理的[算法系列] 深入递归本质+经典例题解析——如何逐步生成, 以此类推,步步为营的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。