深入淺出 Python 中的遞歸算法
一、初識遞歸
遞歸（Recursion）是一種解決問題的思路，其精髓在于將問題分解為規(guī)模更小的相同問題，持續(xù)分解，直到問題規(guī)模小到可以用非常簡單直接的方式來解決。遞歸的問題分解方式非常獨特，其算法方面的明顯特征就是：在算法流程中調(diào)用自身。
遞歸為我們提供了一種對復雜問題的優(yōu)雅解決方案，精妙的遞歸算法常會出奇簡單，令人贊嘆，妙?。?/p>
舉例：給定一個列表，返回其中所有數(shù)的和，列表中數(shù)字的個數(shù)未知，現(xiàn)在既不能用 for 循環(huán)，也不能用 while 循環(huán)，這時可以用遞歸的方法來解決問題！
數(shù)列求和問題具備了基本結(jié)束條件：當列表長度為 1 的時候，直接輸出所包含的唯一數(shù)。 數(shù)列求和處理的數(shù)據(jù)對象是一個列表，而基本結(jié)束條件是長度為 1 的列表，那遞歸算法就要改變列表并向長度為 1 的狀態(tài)演進，代碼實現(xiàn)時具體做法是將列表長度減少1。 調(diào)用自身：實際上可以理解為"問題分解成了規(guī)模更小的相同問題"，在數(shù)列求和算法中就是"更短數(shù)列的求和問題"。 
def sum_n(lst):
return lst[0] if len(lst) <=1 else lst[0] + sum_n(lst[1:])
print(sum_n([1, 3, 5, 7, 9]))
遞歸算法必須要有結(jié)束條件（最小規(guī)模問題的直接解決） 遞歸算法必須能改變狀態(tài)向基本結(jié)束條件演進（減小問題規(guī)模） 遞歸算法必須調(diào)用自身（解決減小了規(guī)模的相同問題）
當一個函數(shù)被調(diào)用的時候，系統(tǒng)會把調(diào)用時的現(xiàn)場數(shù)據(jù)壓入到系統(tǒng)調(diào)用棧。每次調(diào)用，壓入棧的現(xiàn)場數(shù)據(jù)稱為棧幀，當函數(shù)返回時，要從調(diào)用棧的棧頂取得返回地址，恢復現(xiàn)場，彈出棧幀，按地址返回。 在調(diào)試遞歸算法程序的時候經(jīng)常會碰到這樣的錯誤：RecursionError: maximum recursion depth exceeded in comparison，原因遞歸的層數(shù)太多，但系統(tǒng)調(diào)用棧容量是有限的。 
爆棧是非常危險的操作，在實際開發(fā)寫遞歸算法時應盡力避免。Python內(nèi)置的 sys 模塊可以獲取和調(diào)整最大遞歸深度，操作如下：
二、進制轉(zhuǎn)換
十進制有十個不同符號：dec_str="0123456789"，比 10 小的整數(shù)，轉(zhuǎn)換成十進制，直接查表就可以得到：dec_str[n]，把比 10 大的整數(shù)，拆成一系列比十小的整數(shù)，逐個查表，比如七百六十九，拆成七、六、九，查表就可以得到769。 所以，在遞歸三定律里，我們找到了 "基本結(jié)束條件”，就是小于 10 的整數(shù)拆解整數(shù)的過程就是向“基本結(jié)束條件”演進的過程"。 我們用整數(shù)除，和求余數(shù)兩個計算來將整數(shù)一步步拆開，除以 "進制基base"（//base） 對 "進制基" 求余數(shù)（%base）
def dec_conversion_n(n, base):
str_list = "0123456789ABCDEF"
if n < base:
return str_list[n] # 到了最小規(guī)模 查表
else: # 減小規(guī)模 調(diào)用自身
return dec_conversion_n(n // base, base) + str_list[n % base]
print(dec_conversion_n(233, 8))
def dec_conversion_n(n, base):
str_list = "0123456789ABCDEF"
return str_list[n] if n < base else dec_conversion_n(n // base, base) + str_list[n % base]
print(dec_conversion_n(233, 8))
余數(shù)總是小于"進制基base"的，當整數(shù)商小于進制基時，達到遞歸結(jié)束條件，可直接進行查表轉(zhuǎn)換，整數(shù)商成為 "更小規(guī)模" 問題，通過遞歸調(diào)用自身解決，成功利用遞歸的方法來解決進制轉(zhuǎn)換問題。
三、遞歸可視化
import turtle
t = turtle.Turtle()
def draw_spiral(line_len):
if line_len > 0:
t.forward(line_len)
t.right(90)
draw_spiral(line_len - 5)
draw_spiral(160)
turtle.done()
用分形樹能更形象地展現(xiàn)遞歸調(diào)用。分形是在不同尺度上都具有相似性的事物，分形樹特征：子圖結(jié)構(gòu)與自身相似，很容易想到遞歸。
Python中的 turtle 的使用，讓我們能夠很方便地畫出分形樹，畫分形樹的思想也可以用到二叉樹的遍歷中，代碼實現(xiàn)如下：
def draw_tree(branch_len):
if branch_len > 5:
t.forward(branch_len)
t.right(20)
draw_tree(branch_len - 15)
t.left(40)
draw_tree(branch_len - 15)
t.right(20)
t.backward(branch_len)
t = turtle.Turtle()
t.left(90)
t.penup()
t.backward(100)
t.pendown()
t.pencolor('red')
t.pensize(2)
draw_tree(75)
t.hideturtle()
turtle.done()
把樹分解為三個部分：樹干、左邊的小樹、右邊的小樹分解后，正好符合遞歸的定義：對自身的調(diào)用。
謝爾賓斯基三角形（英語：Sierpinski triangle）也是一種分形，由波蘭數(shù)學家謝爾賓斯基在 1915 年提出，它是自相似集的例子。根據(jù)自相似特性，謝爾賓斯基三角形是由 3 個尺寸減半的謝爾賓斯基三角形按照品字形拼疊而成，由于我們無法真正做出謝爾賓斯基三角形（degree趨于無窮），只能做 degree 有限的近似圖形。
在 degree 有限的情況下，degree=n的三角形，是由 3 個 degree=n-1 的三角形，按照品字形拼疊而成。同時，這 3 個 degree=n-1 的三角形邊長均為degree=n的三角形的一半（規(guī)模減?。?。當degree=0，則就是一個等邊三角形，這是遞歸基本結(jié)束條件。作圖如下：
# -*- coding: UTF-8 -*-
"""
@Author ：葉庭云
@公眾號 ：修煉Python
@CSDN ：https://yetingyun.blog.csdn.net/
"""
import turtle
def drawTriangle(points, color, my_turtle): # 繪制等邊三角形
my_turtle.fillcolor(color)
my_turtle.up()
my_turtle.goto(points[0][0], points[0][1])
my_turtle.down()
my_turtle.begin_fill()
my_turtle.goto(points[1][0], points[1][1])
my_turtle.goto(points[2][0], points[2][1])
my_turtle.goto(points[0][0], points[0][1])
my_turtle.end_fill()
def getMid(p1, p2): # 取兩個點的中心
return (p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2
def sierpinski(points, degree, my_turtle):
colormap = ['blue', 'red', 'green', 'white',
'yellow', 'violet', 'orange']
drawTriangle(points, colormap[degree], my_turtle)
if degree > 0:
sierpinski([points[0],
getMid(points[0], points[1]),
getMid(points[0], points[2])],
degree - 1, my_turtle)
sierpinski([points[1],
getMid(points[0], points[1]),
getMid(points[1], points[2])],
degree - 1, my_turtle)
sierpinski([points[2],
getMid(points[2], points[1]),
getMid(points[0], points[2])],
degree - 1, my_turtle)
def main():
myTurtle = turtle.Turtle()
myWin = turtle.Screen()
myPoints = [[-100, -50], [0, 100], [100, -50]] # 外輪廓三個頂點
sierpinski(myPoints, 4, myTurtle) # 畫degree=5的三角形
myWin.exitonclick()
main()
效果如下：
四、漢諾塔問題求解
問題來源：漢諾塔來源于印度傳說的一個故事，上帝創(chuàng)造世界時作了三根金剛石柱子，在一根柱子上從上往下從小到大順序摞著 64 片黃金圓盤。上帝命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一回只能移動一個圓盤，只能移動在最頂端的圓盤。有預言說，這件事完成時宇宙會在一瞬間閃電式毀滅。也有人相信婆羅門至今仍在一刻不停地搬動著圓盤。當然這個傳說并不可信，如今漢諾塔更多的是作為一個玩具存在。
這里推薦一個可以在線玩漢諾塔小游戲的網(wǎng)站：http://www.htmleaf.com/Demo/201508272485.html
移 3 個盤子演示如下：
將盤片塔從開始柱，經(jīng)由中間柱，移動到目標柱：首先將上層 N-1個盤片的盤片塔，從開始柱，經(jīng)由目標柱，移動到中間柱；然后將第N個（最大的）盤片，從開始柱，移動到目標柱。 最后將放置在中間柱的 N-1 個盤片的盤片塔，經(jīng)由開始柱，移動到目標柱?；窘Y(jié)束條件，也就是最小規(guī)模問題變?yōu)椋?個盤片的移動問題。
def move_tower(height, start_pole, mid_pole, target_pole):
if height >= 1:
# 開始柱 目標柱 中間柱
move_tower(height - 1, start_pole, target_pole, mid_pole)
# 記錄移動
move_disk(height, start_pole, target_pole)
# 中間柱 開始柱 目標柱
move_tower(height - 1, mid_pole, start_pole, target_pole)
def move_disk(disk, start_pole, target_pole):
print(f"將 {disk} 號盤子從 {start_pole}號柱 移到 {target_pole}號柱")
move_tower(3, "1", "2", "3") # 2^n - 1次
print("Complete!")
結(jié)果如下：
和動圖里我們玩游戲的操作步驟一致！
五、總結(jié)
遞歸是解決某些具有自相似性的復雜問題的有效方法
遞歸算法必須要有結(jié)束條件（最小規(guī)模問題的直接解決） 遞歸算法必須能改變狀態(tài)向基本結(jié)束條件演進（減小問題規(guī)模） 遞歸算法必須調(diào)用自身（解決減小了規(guī)模的相同問題）
某些情況下，遞歸可以代替迭代循環(huán)，遞歸算法通常能夠跟問題的表達自然契合。 遞歸不總是最合適的算法，有時候遞歸算法會引發(fā)巨量的重復計算，"記憶化/函數(shù)值緩存"可以通過附加存儲空間記錄中間計算結(jié)果來有效減少重復計算（備忘錄技術）。 如果一個問題最優(yōu)解包括規(guī)模更小相同問題的最優(yōu)解，這時我們可以用動態(tài)規(guī)劃來解決。
參考資料如下：
https://www.icourse163.org/course/PKU-1206307812
https://blog.csdn.net/qq_36804363/article/details/88374263
謝爾賓斯基三角形 百度百科
更多閱讀
特別推薦
點擊下方閱讀原文加入社區(qū)會員