深入淺出 Python 中的遞歸算法

一、初識遞歸

遞歸（Recursion）是一種解決問題的思路，其精髓在於將問題分解爲規模更小的相同問題，持續分解，直到問題規模小到可以用非常簡單直接的方式來解決。遞歸的問題分解方式非常獨特，其算法方面的明顯特徵就是：在算法流程中調用自身。

遞歸爲我們提供了一種對複雜問題的優雅解決方案，精妙的遞歸算法常會出奇簡單，令人讚歎，妙啊！

舉例：給定一個列表，返回其中所有數的和，列表中數字的個數未知，現在既不能用 for 循環，也不能用 while 循環，這時可以用遞歸的方法來解決問題！

思路：

數列求和問題具備了基本結束條件：當列表長度爲 1 的時候，直接輸出所包含的唯一數。
數列求和處理的數據對象是一個列表，而基本結束條件是長度爲 1 的列表，那遞歸算法就要改變列表並向長度爲 1 的狀態演進，代碼實現時具體做法是將列表長度減少 1。
調用自身：實際上可以理解爲 "問題分解成了規模更小的相同問題"，在數列求和算法中就是 "更短數列的求和問題"。

遞歸實現數列求和如下：

1def sum_n(lst):
2     return lst[0] if len(lst) <=1 else lst[0] + sum_n(lst[1:])
3
4print(sum_n([1, 3, 5, 7, 9]))
5
6

遞歸算法三定律：

遞歸算法必須要有結束條件（最小規模問題的直接解決）
遞歸算法必須能改變狀態向基本結束條件演進（減小問題規模）
遞歸算法必須調用自身（解決減小了規模的相同問題）

遞歸調用的實現：

當一個函數被調用的時候，系統會把調用時的現場數據壓入到系統調用棧。每次調用，壓入棧的現場數據稱爲棧幀，當函數返回時，要從調用棧的棧頂取得返回地址，恢復現場，彈出棧幀，按地址返回。
在調試遞歸算法程序的時候經常會碰到這樣的錯誤：RecursionError: maximum recursion depth exceeded in comparison，原因遞歸的層數太多，但系統調用棧容量是有限的。

爆棧是非常危險的操作，在實際開發寫遞歸算法時應盡力避免。Python 內置的 sys 模塊可以獲取和調整最大遞歸深度，操作如下：

二、進制轉換

十進制有十個不同符號：dec_str="0123456789"，比 10 小的整數，轉換成十進制，直接查表就可以得到：dec_str[n]，把比 10 大的整數，拆成一系列比十小的整數，逐個查表，比如七百六十九，拆成七、六、九，查表就可以得到 769。
所以，在遞歸三定律裏，我們找到了 "基本結束條件”，就是小於 10 的整數拆解整數的過程就是向 “基本結束條件” 演進的過程"。
我們用整數除，和求餘數兩個計算來將整數一步步拆開，除以 "進制基 base"（//base）對 "進制基" 求餘數（%base）

遞歸實現如下：

 1def dec_conversion_n(n, base):
 2    str_list = "0123456789ABCDEF"
 3    if n < base:
 4        return str_list[n]  # 到了最小規模  查表
 5    else:   # 減小規模  調用自身
 6        return dec_conversion_n(n // base, base) + str_list[n % base]
 7
 8print(dec_conversion_n(233, 8))
 9
10

結果如下：

玩 Python 嘛，還可以寫得更優雅一些：

1def dec_conversion_n(n, base):
2    str_list = "0123456789ABCDEF"
3    return str_list[n] if n < base else dec_conversion_n(n // base, base) + str_list[n % base]
4
5print(dec_conversion_n(233, 8))
6
7

餘數總是小於 "進制基 base" 的，當整數商小於進制基時，達到遞歸結束條件，可直接進行查錶轉換，整數商成爲 "更小規模" 問題，通過遞歸調用自身解決，成功利用遞歸的方法來解決進制轉換問題。

三、遞歸可視化

通過可視化來形象地展現遞歸調用：

 1import turtle
 2
 3t = turtle.Turtle()
 4def draw_spiral(line_len):
 5    if line_len > 0:
 6        t.forward(line_len)
 7        t.right(90)
 8        draw_spiral(line_len - 5)
 9
10draw_spiral(160)
11turtle.done()
12
13

用分形樹能更形象地展現遞歸調用。分形是在不同尺度上都具有相似性的事物，分形樹特徵：子圖結構與自身相似，很容易想到遞歸。Python 中的 turtle 的使用，讓我們能夠很方便地畫出分形樹，畫分形樹的思想也可以用到二叉樹的遍歷中，代碼實現如下：

 1def draw_tree(branch_len):
 2    if branch_len > 5:
 3        t.forward(branch_len)
 4        t.right(20)
 5        draw_tree(branch_len - 15)
 6        t.left(40)
 7        draw_tree(branch_len - 15)
 8        t.right(20)
 9        t.backward(branch_len)
10
11
12t = turtle.Turtle()
13t.left(90)
14t.penup()
15t.backward(100)
16t.pendown()
17t.pencolor('red')
18t.pensize(2)
19draw_tree(75)
20t.hideturtle()
21turtle.done()
22
23

效果如下：

把樹分解爲三個部分：樹幹、左邊的小樹、右邊的小樹分解後，正好符合遞歸的定義：對自身的調用。

謝爾賓斯基三角形（英語：Sierpinski triangle）也是一種分形，由波蘭數學家謝爾賓斯基在 1915 年提出，它是自相似集的例子。根據自相似特性，謝爾賓斯基三角形是由 3 個尺寸減半的謝爾賓斯基三角形按照品字形拼疊而成，由於我們無法真正做出謝爾賓斯基三角形（degree 趨於無窮），只能做 degree 有限的近似圖形。

在 degree 有限的情況下，degree=n 的三角形，是由 3 個 degree=n-1 的三角形，按照品字形拼疊而成。同時，這 3 個 degree=n-1 的三角形邊長均爲 degree=n 的三角形的一半（規模減小）。當 degree=0，則就是一個等邊三角形，這是遞歸基本結束條件。作圖如下：

 1# -*- coding: UTF-8 -*-
 2"""
 3@Author  ：葉庭雲
 4@公衆號  ：修煉Python
 5@CSDN    ：https://yetingyun.blog.csdn.net/
 6"""
 7import turtle
 8
 9
10def drawTriangle(points, color, my_turtle):   # 繪製等邊三角形
11    my_turtle.fillcolor(color)
12    my_turtle.up()
13    my_turtle.goto(points[0][0], points[0][1])
14    my_turtle.down()
15    my_turtle.begin_fill()
16    my_turtle.goto(points[1][0], points[1][1])
17    my_turtle.goto(points[2][0], points[2][1])
18    my_turtle.goto(points[0][0], points[0][1])
19    my_turtle.end_fill()
20
21
22def getMid(p1, p2):       # 取兩個點的中心
23    return (p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2
24
25
26def sierpinski(points, degree, my_turtle):
27    colormap = ['blue', 'red', 'green', 'white',
28                'yellow', 'violet', 'orange']
29    drawTriangle(points, colormap[degree], my_turtle)
30    if degree > 0:
31        sierpinski([points[0],
32                    getMid(points[0], points[1]),
33                    getMid(points[0], points[2])],
34                   degree - 1, my_turtle)
35        sierpinski([points[1],
36                    getMid(points[0], points[1]),
37                    getMid(points[1], points[2])],
38                   degree - 1, my_turtle)
39        sierpinski([points[2],
40                    getMid(points[2], points[1]),
41                    getMid(points[0], points[2])],
42                   degree - 1, my_turtle)
43
44
45def main():
46    myTurtle = turtle.Turtle()
47    myWin = turtle.Screen()
48    myPoints = [[-100, -50], [0, 100], [100, -50]]   # 外輪廓三個頂點
49    sierpinski(myPoints, 4, myTurtle)   # 畫degree=5的三角形
50    myWin.exitonclick()
51
52
53main()
54
55

效果如下：

四、漢諾塔問題求解

問題來源：漢諾塔來源於印度傳說的一個故事，上帝創造世界時作了三根金剛石柱子，在一根柱子上從上往下從小到大順序摞着 64 片黃金圓盤。上帝命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一回只能移動一個圓盤，只能移動在最頂端的圓盤。有預言說，這件事完成時宇宙會在一瞬間閃電式毀滅。也有人相信婆羅門至今仍在一刻不停地搬動着圓盤。當然這個傳說並不可信，如今漢諾塔更多的是作爲一個玩具存在。

這裏推薦一個可以在線玩漢諾塔小遊戲的網站：http://www.htmleaf.com/Demo/201508272485.html

移 3 個盤子演示如下：

思路：

將盤片塔從開始柱，經由中間柱，移動到目標柱：首先將上層 N-1 個盤片的盤片塔，從開始柱，經由目標柱，移動到中間柱；然後將第 N 個（最大的）盤片，從開始柱，移動到目標柱。
最後將放置在中間柱的 N-1 個盤片的盤片塔，經由開始柱，移動到目標柱。基本結束條件，也就是最小規模問題變爲：1 個盤片的移動問題。

遞歸實現的 Python 代碼如下：

 1def move_tower(height, start_pole, mid_pole, target_pole):
 2    if height >= 1:
 3        # 開始柱  目標柱  中間柱
 4        move_tower(height - 1, start_pole, target_pole, mid_pole)
 5        # 記錄移動
 6        move_disk(height, start_pole, target_pole)
 7        # 中間柱  開始柱  目標柱
 8        move_tower(height - 1, mid_pole, start_pole, target_pole)
 9
10def move_disk(disk, start_pole, target_pole):
11    print(f"將 {disk} 號盤子從 {start_pole}號柱 移到 {target_pole}號柱")
12
13move_tower(3, "1", "2", "3")    # 2^n - 1次
14print("Complete!")
15
16

結果如下：和動圖裏我們玩遊戲的操作步驟一致！

五、總結

遞歸是解決某些具有自相似性的複雜問題的有效方法

遞歸算法三定律：

遞歸算法必須要有結束條件（最小規模問題的直接解決）
遞歸算法必須能改變狀態向基本結束條件演進（減小問題規模）
遞歸算法必須調用自身（解決減小了規模的相同問題）

注意：

某些情況下，遞歸可以代替迭代循環，遞歸算法通常能夠跟問題的表達自然契合。
遞歸不總是最合適的算法，有時候遞歸算法會引發巨量的重複計算，"記憶化 / 函數值緩存" 可以通過附加存儲空間記錄中間計算結果來有效減少重複計算（備忘錄技術）。
如果一個問題最優解包括規模更小相同問題的最優解，這時我們可以用動態規劃來解決。

https://blog.csdn.net/qq_36804363/article/details/88374263

謝爾賓斯基三角形百度百科

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/_pIzIFieFg_8v3AqJatKNA

一、初識遞歸

二、進制轉換

三、遞歸可視化

四、漢諾塔問題求解

五、總結

猜你喜歡