[算法系列] 搞懂遞歸, 看這篇就夠了 !! 遞歸設計思路 + 經典例題層層遞進
從學習寫代碼伊始, 總有個坎不好邁過去, 那就是遇上一些有關遞歸的東西時, 看着簡短的代碼, 怎麼稀裡糊塗就出來了. 今天我們就來好好好探讨
遞歸
這個東西. 本文結合他的相關概念,引出有關遞歸程式設計的一些例子,并加以說明, 其旨在更好地了解遞歸,使用遞歸.
0 什麼是遞歸?
很多文章對于遞歸有很深刻的字面上的解釋, 比如一個函數重複調用自身, 什麼遞過去再調回來之類的. 下面, 我們從自身調用來談起吧 :
def f(i):
f(i-1)
f(5)
在f()定義中自身調用了f , 并将之前的參數i - 1 傳入f . 是以不難知道 f(5)運作時是這樣的 :
f(5) --> f(4) --> f(3) --> f(2) --> ... f(-∞)
不斷地調用自身, 并且參數減1. 單純地這樣調用實際上并不滿足遞歸, 當然, 我們的問題也不可能得以解決的哦.
回到設計程式初 :
我們設計程式時, 這個傳入參數 i 是我們為解決眼前問題時的規模 , i - 1 是小一号的問題的規模. 比如: 我們令f(i) 為 某人花掉 i 元錢 . 那麼f(i) 在自身 調用f(i - 1) 時相當于 自己先花掉1 元後 ,将剩下的 i - 1元錢給另一個人用. 顯然, 錢不可能為負, 是以總有被花光的時刻(i = 0 時應當終止), 相應的, 重複自身調用也有終止的一刻 , 也即是說,
遞歸要有出口:
def f(i):
if i == 0 :
return
f(i - 1)
在花錢函數中增加了一個判斷 , 如果i =0 了 ,就return. 這就表示當一個人拿到錢的數目為0 , 他得上報(return)給之前調用給他的那個人,然後層層上報, 報給最初的那個人.
與此同時, 我們在縮減問題規模時, 可能并不是像上述例程那樣, 什麼都不做就直接i - 1 , 而是會"花一塊錢" , 這其實就是我們所說的遞歸的
副作用. 注意, 這是我們在問題規模減小時所加的副作用, 當錢用光了,層層上報時 , 能不能也有副作用呢? 答案是顯然是肯定的. 我喜歡把這兩種副作用稱之為
遞過去過程中的副作用和
歸回來過程中的副作用上述部分說明了:
- 什麼是遞歸 ----- 函數自己調用自己.
- 注意死循環 ------ 遞歸要有出口
- 遞歸往往有副作用 ----- 遞過去途中 的 和 歸來途中, 其中遞過去往往是 問題規模縮小 的過程, 歸來過程是已經觸及到出口後的傳回
知道了什麼是遞歸那麼我們怎麼來設計遞歸呢?
- 找重複, 思考問題規模如何縮小
- 找變化
- 找邊界, 就是遞歸出口了
下面為了更好地體會下遞歸并說明上述三條 , 将下列問題用遞歸方式表達
求n的階乘
- 找重複: n的階乘 = n * (n - 1的階乘), 那麼 求 "n - 1的階乘"就是原問題的重複 -- 子問題
- 找變化: 這裡就是n的量越變越小 -- 變化的量往往作為參數
- 找邊界: 出口, 找一個數的階乘, 不可能小于1
def jiecheng(n):
if(n == 1 ):
return 1
return n * jiecheng(n - 1)
順序列印 i 到 j ( i <= j , 包含j)
這個問題顯然可以不用遞歸方式來做, 但是這裡正是通過使用遞歸來體會:
自己做一部分, 剩下的交給别人按同樣的方式來處理, 然後等待處理結果, 再加上自己處理的結果- 找重複:
- 找變化: 這裡就是n的量越變越小 -- 變化的量往往作為參數
- 找邊界: 出口, 即 i = j 時
def print_i_j(i , j ):
if(i > j):
return
print(i)
print_i_j(i +1 , j)
我們再看看這個遞歸寫法: 在沒到達出口條件時: 先列印出i , 再調用 小一号規模的問題. 下面是調用結果:
print_i_j(1,10)
#1 2 3 4 5 6 7 8 9 10
倒序列印 i 到 j ( i <= j , 包含j)
實際上, 我隻需在上述代碼中調換下列印順序即可解決該問題:
def print_i_j(i , j ):
if(i > j):
return
print_i_j(i +1 , j)
print(i, end=" ")
現在來分析下print(i)放在下一次調用之前和之後的情況:
- 順序列印: 先列印出i ,再自身調用小一号規模的子問題, 這就相當于是自己先處理一些,剩下的交給其他人處理(先花1元錢, 剩下的交給下一個人花) . 這也就是所謂的 在遞出去時産生的副作用
- 倒序列印: 先調用小一号的子問題, 由于在自身調用前, 也就是"遞出去時"沒有其餘動作, 重複調用會直至遞歸出口, 然後依次傳回, 子函數在反回到父函數時會接着父函數調用位置的下一行繼續執行, 這就是所謂的 在歸回來的産生的副作用 .
倒序時, 先一鼓作氣走到了 i > j 然後傳回這一輪的父函數中, 此時是 i = j ,緊接着print(i) 也就是j 的值了 , 然後再傳回他的父函數中, i = j - 1 ,列印的也就是倒數第二個數了.
下面我們繼續
對數組 arr 所有元素進行求和
這個很顯然也是可以 for 循環進行, 不過我們就是要改成遞歸, 體會自己做一部分工作, 剩下的(小一号規模的子問題)交給和自己具有相同功能的人(自我調用)來做.
下面是該問題的一個設計思考
def sum(arr):
...
發現我們很在在遞歸内部繼續寫, 這是為什麼呢? 原因就在于, 這個arr參數是不變的 . 參考:
找變化: 變化的量往往作為參數這一點. 在求和範圍不斷縮小時, 我們需要一個參數去描述
我們需要在不變中追求統一, 在變化中尋求突破(出口)(是不是很哲學♂ )
def sum(arr , begin):
if begin == len(arr) - 1:
return arr[begin]
return arr[begin] + sum(arr , begin + 1)
在遞歸中, begin從0開始不斷地增加, 直到到達最後一個元素下标為止.
上述例子也就很好的說明了遞歸中的變與不變, 而
在變化中添加參數也是遞歸設計的難點, 下面再來個這種例子:
給定一個字元串,将其翻轉
例如輸入: "abcd" , 輸出"dcba"
def reverse(str , end):
if end == 0:
return str[0]
return str[end] +reverse(str , end - 1)
end從str的最後一位下标開始往回,直到0
現在,各位有無對遞歸設計思想中的 :
變化中尋找重複構以成遞歸, 重複中尋找變化以靠近出口有了更深的了解了呢?
前面的遞歸設計中, 我們可以将其統稱為:
求解f(N),我們自己做一部分x, 其他的交給和我同樣功能的人做f(N- 1),直到分不了為止. 換句話說, 為求解f(N),我們可以先求解縮小一次規模的問題f(N-1), 加之一些副作用x. 如下:
f(N) = x + f(N - 1)
在遞歸中, 除了上面那種縮小一點問題規模,帶點副作用,再縮小 ... 還有将問題 拆分成兩個子問題去分别求解的,比如:
f(N) = f(N/2) + f(N/2) + X #将問題N拆成兩半,分别求解f(N/2)
f(N) = f(N - 1) + f(N - 2) + x #為求解f(N),需要的比現在小1号的子問題f(N-1)和小2号的子問題f(N-2)
f(N) = f(N/k) + f(N/k) + f(N/k) + ...
求第n 個斐波那契數列元素
斐波那契數列 1,1,2,3,5,8,13 ,... , 我們發現從第三項開始, 該位置上的值等于其前面兩個位置值的和
即有天然的 f(n) = f(n - 1) + f(n -2) ,當n >= 3時, 當要求解n時, 我們隻需要分别求解n-1 和 n - 2 的結果,再相加即可.
def fibo(n):
if n <= 2:
return 1
return fibo(n -1) + fibo(n -2)
print(fibo(6))
這裡面的出口即為n = 1或者2 時, 他們是天然等于1的. 變化的即為這個n 了 ,不變的是求解方法: 每一項等于前面兩項的和.
(細心的同學可以發現, 每次我們在求f(n -1) 和 f(n -2)時 ,是
分别進行遞歸的, 是以很多東西實際上是重複計算了的, 而f(n - 1) 實際上隻需要f(n-2) + (n-1)即可求得, 這其實涉及到記事本方法, 也是dp方法的一個重要例子, 以後有機會會繼續更新的~~)
求解最大公約數
兩個數m , n ,若 m % n = 0 則n為兩個數的最大公約數 (出口)
若 m % n = k (k != 0) 則求 n % k (變化)
def gcd(m ,n ):
if n == 0:
return m
return gcd(n , m%n)
插入排序的遞歸形式
# 插入排序的遞歸形式
def insert_sort(arr , k):
if k == 0 :
return ;
#對前n -1 個元素排序
insert_sort(arr, k -1)
# 把位置k的元素插入到前面的部分
x = arr[k]
index = k -1
while index > -1 and x <arr[index] :
arr[index + 1] = arr[index]
index -= 1
arr[index+1] = x
大體思路和非遞歸的循環式的差不多, 遞歸式的是先從k=len -1出發, 然後徑直走到0處, 依次向前插到合适的位置, 逐漸歸回來,即k增加.
遞歸設計思路小結: 找重複:- 找到一種劃分成更小規模問題的方法, 或者是單個劃分,或者是多個劃分, 另外也可能選擇劃分
- 找到遞推公式或者等價轉換
變化的量通常會作為參數,(循環的過程也是變化) 找出口:
變化的極限往往就是出口.(循環的中點就是出口)漢諾塔問題
文字描述:
将 1 ~ N 從A 移動到B, C作為輔助. 要求一次隻能移一個, 小的不能在大的下面 (最下面一個為N)
按照思路小結,先嘗試把問題規模縮小, 找一種劃分方法:
- 考慮把1 和 2 ~ N 劃分開 . 那麼完成這件事情需要三個步驟:
- 把 1 直接從A挪到C
- 把 2 ~ N 從A挪到B , C作為輔助
- 把 1 直接從C挪到B
現在重點關注第2點, 考慮: 把2 ~ N 挪到B 這一事件是否是把1 ~ N 挪到B的子問題呢?
我們發現, 把1 ~ N 挪到B , B和C都為空, 兩個位置都能放盤子, 但在2 ~ N 從A挪到B時 , C上面有1, 根據題意小盤上面不能放大盤, 是以此時2 ~ N不能往C上放.
該問題的局面與初始不同, 第2點并不是原題等價縮小的規模- 考慮把1 ~ N -1 和 N 劃分開, 那麼完成該事情同樣需要三個步驟:
- 把1 ~ N -1 從 A 挪到 C上 , B 作為輔助
- 把 N 從直接 A 挪到 B 上
- 把1 ~ N -1 從C 挪到 B 上 , A 作為輔助
類似的, 我們關注第1 , 3 是否為1 ~ N 從A 挪到B的子問題.
顯然, 把1 ~ N -1 從A挪到C具有相同的局面(其餘兩個位置随便放). 把1 ~ N -1 從C 挪到B需要考慮下: 此時 N 在 B 上, 但是他是最大的, 對于在C上的1 ~ N -1 , 也是A,B兩個位置都能放的, 由此可見, 此處問題即上一個的子問題.
各位現在可以看看漢諾塔文字描述的加粗部分和上面的1,3, 子問題規模性已經說明.
接下來嘗試找變化, 從上述加粗的子問題父問題描述我們發現 ,變化的其實包括有
待轉移盤個數N 變為N -1 ,
從哪轉移到哪(from A to C), 那好 ,把這些作為參數.
最後考慮出口, 顯然, 當N =1 時 , 直接從A移動到B即可.
def hano_tower(N , src , dis , help):
'''
:param N: 初始的N個從小到大的盤子, N 是最大編号
:param src: 原始位置
:param dis: 目标位置
:param help: 輔助位置
'''
if N == 1:
print("移動第 " + str(N) + " 個盤子, 從 " + src + " 到 "+ dis)
return
else:
hano_tower(N -1 , src , help , dis) #先把 N - 1 個盤子挪到輔助空間
print("移動第 " + str(N) + " 個盤子, 從 " + src + " 到 " + dis)
hano_tower(N -1 , help , dis , src) #先把 N - 1 個盤子挪到輔助空間
hano_tower(3 , "A" , "B" , "C")
#控制台輸出
移動第 1 個, 從 A 到 B
移動第 2 個, 從 A 到 C
移動第 1 個, 從 B 到 C
移動第 3 個, 從 A 到 B
移動第 1 個, 從 C 到 A
移動第 2 個, 從 C 到 B
移動第 1 個, 從 A 到 B
二分查找的遞歸法
等價為子問題:
- 左邊找 (遞歸)
- 中間找 (是否等于中間那個數)
-
右邊找 (遞歸)
注意, 左查找和右查找隻選其一
變化的量, 左右兩邊界low, high作為參數. 變化中, 兩者靠近, 當low > high 時 或者 找到了k 時即為出口
```python def binary_search(k,arr, low, high): mid = int((low + high) /2) if(low > high): return -1 if arr[mid] == k: return mid elif arr[mid] > k: return binary_search(k ,arr , low , mid - 1 ) else: return binary_search(k ,arr , mid +1, high )
bin_arr = [1,2,3,5,6,7,9,11,13,16] print(binary_search( 7, bin_arr, 0 , len(bin_arr) - 1)) ```
以上是一些熟悉的例子, 通過一些常見的問題修改成遞歸形式的過程中, 了解了遞歸設計的方法, 下面是一些經典的遞歸設計練習
1. 青蛙上樓梯
樓梯有n個台階, 一個青蛙一次可以上1 , 2 或3 階 , 實作一個方法, 計算該青蛙有多少種上完樓梯的方法
令f(n) 為 青蛙上n階的方法數. 則f(n) = f(n -1) +f(n - 2) + f(n -3) , 當n >= 3
什麼意思呢? 假如青蛙上10 階, 那麼其實相當于要麼 站在第9 階向上走1步,要麼 站在第8 階向上走兩步, 要麼在第7階向上走3步.
進一步來說, 青蛙在到達第10階的方法數, 即為到達第9階的方法數加上到第8階的方法數上加第7階的方法數的和, 則有子問題:
求解f(n):
求解f(n-1)
求解f(n-2)
求解f(n-3)
三者相加
找變化: 變化的即為台階數n
找出口: 當n = 0 時 ,青蛙不動 , f(0) = 0; n = 1時 ,有1種方法 , n = 2 時 有2 種方法
def go_stairs(n):
if n == 0 :
return 0
if n == 1:
return 1
if n == 2:
return 2
return go_stairs(n - 1) +go_stairs(n - 2) +go_stairs(n -3)
2 . 旋轉數組的最小數字
把一個數組最開始的若幹個元素搬到數組的末尾, 我們稱之為數組的旋轉, 輸入一個遞增排序的數組的一個旋轉, 輸出旋轉數組的最小元素. 例如{3,4,5,1,2}是{1,2,3,4,5}的一個旋轉, 該數組的最小值為1.
def reverse_min(arr):
begin = 0
end = len(arr) - 1
# 考慮沒有旋轉的 情況
if arr[begin] < arr[end] :
return arr[begin]
# begin 和 end 指向相鄰元素時,退出
while begin + 1 < end :
mid = int((begin + end) / 2)
# 要麼左側有序, 要麼右側有序
if arr[mid] >= arr[begin]: #左側有序, 在右邊找
begin = mid;
else:
end = mid
return arr[end]
3. 設計一個高效的求a的n次方幂的算法
def pow(a , n):
if n == 0 :
return 1
res = a
ex = 1
while (ex << 1 ) <= n: # 翻倍後還小于n的話直接翻倍
res= res * res
ex =ex * 2
# 差n-ex次方還沒有乘上結果
return res * pow(a , n - ex) #将翻不動時的剩餘的作為參數帶到下一次運作
下一篇文章中, 我們将讨論遞歸的應用 -- 分治法(結合我們熟悉的快排和歸排) . 應該說, 遞歸是一種程式設計形式, 而分治法是常常使用遞歸形式的一種算法.
原文: lawfree的CSDN部落格:[算法系列] 搞懂遞歸, 看這篇就夠了 !! 遞歸設計思路 + 經典例題層層遞進