Python資料結構之遞迴視覺化詳解

2022-04-15 19:01:08

1.學習目標

遞迴函數是直接呼叫自己或通過一系列語句間接呼叫自己的函數。遞迴在程式設計有著舉足輕重的作用，在很多情況下，藉助遞迴可以優雅的解決問題。雖然使用遞迴可以快速的解決一些難題，但由於遞迴的抽象性，使遞迴難以掌握。為了更好的理解遞迴函數背後的思想，本節主要通過視覺化方式來了解遞迴函數的執行步驟。

通過本節學習，應掌握以下內容：

提高對遞迴的理解

利用視覺化理解遞迴函數背後的思想

2.遞迴的呼叫

雖然使用遞迴可以快速的解決一些難題，但由於遞迴的抽象性，使得遞迴難以掌握。雖然已經在《遞迴基礎》中講解了遞迴的範例，並且簡單的瞭解了遞迴的呼叫過程，但缺乏具體的認知。本節將對遞迴的呼叫進行更加深入的講解。

遞迴函數執行時，每次遞迴呼叫都會在記憶體中建立新的函數副本，一旦函數呼叫結束，則返回一些資料，並將此副本就會從記憶體中刪除。通常，遞迴方法得到的解決方案看起來十分簡潔簡單，但理解並跟蹤函數的執行卻較為複雜。為了更好地理解，考慮以下求取斐波那契數列的簡單範例：

def fibo(n):
    if n == 0:
        return 1
    else:
        return n * fibo(n - 1)
def main():
    number = 4
    result = fibo(number)
    print(result)
if __name__ == "__main__":
    main()

當程式執行到第 10 行時。第一次呼叫 fibo() 函數，會為 fibo() 函數呼叫建立一條新的活動記錄，此時在執行時棧上具有 3 條活動記錄。然後 Python 直譯器跳轉到第 2 行，其中 n 指向數位 4，如下圖所示。n 不等於 0，因此跳轉到第 5 行，其中包含一個對 fibo() 的函數呼叫，這將在執行時堆疊上建立另一個活動記錄。重複上述過程，直到 n=0。

需要注意的是，每個遞迴函數呼叫都有一個變數 n 的副本。活動記錄儲存函數範圍內的所有區域性變數和引數。每次呼叫函數時，都會建立一個新的活動記錄，並將區域性變數的新副本儲存在活動記錄中，程式執行過程的呼叫順序如下圖所示：

當函數執行到 n=0 時，fibo() 函數返回了它的第一個值，它將 1 返回到上一個函數呼叫。如下圖所示，從執行時堆疊中彈出 n=0 時函數呼叫的活動記錄(通過將圖中活動記錄的變為灰色來表示)。當函數返回時，活動記錄的空間被回收以供以後使用。堆上的陰影物件 0 也被垃圾收集器回收，因為不再有指向它的參照。

在第一次 fibo() 函數返回之後，Python 直譯器返回到前一個函數呼叫中的第 5 行，這個語句也包含一個 return 語句，所以函數再次返回到第 5 行，返回值為 1。同樣，函數再次返回，但這次的值為 2。按照上述過程，直到 fibo() 函數返回到 main() 函數的第 8 行，整個過程如下圖所示：

最後，程式列印執行結果，在第 9 行之後從 main() 函數返回，在第 11 行後從 module 返回並終止。從以上範例可以看出，對 fibo() 函數的每次遞迴呼叫都會建立自己的變數副本。每次呼叫該函數時，都會將區域性變數和引數複製到相應的活動記錄中。當函數呼叫返回時，相應的活動記錄會從執行時堆疊中彈出。這就是遞迴函數的執行方式。

3.遞迴視覺化

本節將利用 turtle 庫遞迴的繪製圖案，提高對遞迴過程的認識。

3.1 turtle 庫簡介

turtle 庫屬於是python的標準庫，通常用於繪製圖案，可以使用該庫建立一隻小烏龜 (turtle) 在畫布上移動，當小烏龜爬行時會在畫布上繪製線條，而當前尾巴擡起時，並不會進行繪製。

接下來，我們將介紹一些基本的 turtle 繪圖函數：

turtle.penup(): turtle 擡起尾巴，之後的移動並不在圖上進行繪製
turtle.pendown()：turtle 放下尾巴，開始爬行，之後會在圖上繪製其行動軌跡
turtle.pensize(width)：用於改變畫筆的寬度
turtle.pencolor(color)：用於改變畫筆顏色
turtle.forward(distance)：向前移動 distance
turtle.back(distance)：向後移動 distance

3.1 遞迴繪圖

首先通過建立一個簡單的遞迴函數 draw() 來了解 turtle 庫，這個遞迴函數的基本情況為——要畫的線長 distance 降為 0；若線長大於 0，就讓小烏龜小烏龜向前繪製 distance 個單位距離，然後左轉 30 度；遞迴情況為——縮短後的距離再次呼叫 draw() 函數。

# 匯入 turtle 庫
import turtle
# 建立小烏龜物件
my_turtle = turtle.Turtle()
# 建立使用者繪製圖案的視窗
window = my_turtle.getscreen()

def draw(turtle, distance):
    if distance > 0:
        # 小烏龜向前繪製 distance 個單位距離
        turtle.forward(distance)
        # 然後左轉 30 度
        turtle.left(30)
        draw(turtle, distance-6)
draw(my_turtle, 200)
window.exitonclick()

接下來，我們使用 turtle 模組繪製分形樹。分形樹和遞迴有許多的共同點，是數學中的一個概念，無論放大多少倍觀察分形圖，總能看到相同的基本形狀。

如果我們定義樹為包含向左生長的子樹和向右生長的子樹的話，就可以根據遞迴的思想得到分形樹：

import turtle
def tree(branch, turtle):
    if branch > 5:
        turtle.forward(branch)
        turtle.right(20)
        tree(branch-15, turtle)
        turtle.left(40)
        tree(branch-10, turtle)
        turtle.right(20)
        turtle.backward(branch)
my_turtle = turtle.Turtle()
window = my_turtle.getscreen()
my_turtle.left(90)
my_turtle.up()
my_turtle.backward(300)
my_turtle.down()
tree(110, my_turtle)
window.exitonclick()

到此這篇關於Python資料結構之遞迴視覺化詳解的文章就介紹到這了,更多相關Python遞迴視覺化內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！