1.學習目標

遞歸函數(shù)是直接調(diào)用自己或通過一系列語句間接調(diào)用自己的函數(shù)。遞歸在程序設計有著舉足輕重的作用，在很多情況下，借助遞歸可以優(yōu)雅的解決問題。雖然使用遞歸可以快速的解決一些難題，但由于遞歸的抽象性，使遞歸難以掌握。為了更好的理解遞歸函數(shù)背后的思想，本節(jié)主要通過可視化方式來了解遞歸函數(shù)的執(zhí)行步驟。

通過本節(jié)學習，應掌握以下內(nèi)容：

提高對遞歸的理解

利用可視化理解遞歸函數(shù)背后的思想

2.遞歸的調(diào)用

雖然使用遞歸可以快速的解決一些難題，但由于遞歸的抽象性，使得遞歸難以掌握。雖然已經(jīng)在《遞歸基礎》中講解了遞歸的示例，并且簡單的了解了遞歸的調(diào)用過程，但缺乏具體的認知。本節(jié)將對遞歸的調(diào)用進行更加深入的講解。

遞歸函數(shù)執(zhí)行時，每次遞歸調(diào)用都會在內(nèi)存中創(chuàng)建新的函數(shù)副本，一旦函數(shù)調(diào)用結束，則返回一些數(shù)據(jù)，并將此副本就會從內(nèi)存中刪除。通常，遞歸方法得到的解決方案看起來十分簡潔簡單，但理解并跟蹤函數(shù)的執(zhí)行卻較為復雜。為了更好地理解，考慮以下求取斐波那契數(shù)列的簡單示例：

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 行時。第一次調(diào)用 fibo() 函數(shù)，會為 fibo() 函數(shù)調(diào)用創(chuàng)建一條新的活動記錄，此時在運行時棧上具有 3 條活動記錄。然后 Python 解釋器跳轉到第 2 行，其中 n 指向數(shù)字 4，如下圖所示。n 不等于 0，因此跳轉到第 5 行，其中包含一個對 fibo() 的函數(shù)調(diào)用，這將在運行時堆棧上創(chuàng)建另一個活動記錄。重復上述過程，直到 n=0。

需要注意的是，每個遞歸函數(shù)調(diào)用都有一個變量 n 的副本?；顒佑涗洷４婧瘮?shù)范圍內(nèi)的所有局部變量和參數(shù)。每次調(diào)用函數(shù)時，都會創(chuàng)建一個新的活動記錄，并將局部變量的新副本存儲在活動記錄中，程序運行過程的調(diào)用順序如下圖所示：

當函數(shù)執(zhí)行到 n=0 時，fibo() 函數(shù)返回了它的第一個值，它將 1 返回到上一個函數(shù)調(diào)用。如下圖所示，從運行時堆棧中彈出 n=0 時函數(shù)調(diào)用的活動記錄(通過將圖中活動記錄的變?yōu)榛疑珌肀硎?。當函數(shù)返回時，活動記錄的空間被回收以供以后使用。堆上的陰影對象 0 也被垃圾收集器回收，因為不再有指向它的引用。

在第一次 fibo() 函數(shù)返回之后，Python 解釋器返回到前一個函數(shù)調(diào)用中的第 5 行，這個語句也包含一個 return 語句，所以函數(shù)再次返回到第 5 行，返回值為 1。同樣，函數(shù)再次返回，但這次的值為 2。按照上述過程，直到 fibo() 函數(shù)返回到 main() 函數(shù)的第 8 行，整個過程如下圖所示：

最后，程序打印執(zhí)行結果，在第 9 行之后從 main() 函數(shù)返回，在第 11 行后從 module 返回并終止。從以上示例可以看出，對 fibo() 函數(shù)的每次遞歸調(diào)用都會創(chuàng)建自己的變量副本。每次調(diào)用該函數(shù)時，都會將局部變量和參數(shù)復制到相應的活動記錄中。當函數(shù)調(diào)用返回時，相應的活動記錄會從運行時堆棧中彈出。這就是遞歸函數(shù)的執(zhí)行方式。

3.遞歸可視化

本節(jié)將利用 turtle 庫遞歸的繪制圖案，提高對遞歸過程的認識。

3.1 turtle 庫簡介

turtle 庫屬于是python的標準庫，通常用于繪制圖案，可以使用該庫創(chuàng)建一只小烏龜 (turtle) 在畫布上移動，當小烏龜爬行時會在畫布上繪制線條，而當前尾巴抬起時，并不會進行繪制。

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

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

3.1 遞歸繪圖

首先通過創(chuàng)建一個簡單的遞歸函數(shù) draw() 來了解 turtle 庫，這個遞歸函數(shù)的基本情況為——要畫的線長 distance 降為 0；若線長大于 0，就讓小烏龜小烏龜向前繪制 distance 個單位距離，然后左轉 30 度；遞歸情況為——縮短后的距離再次調(diào)用 draw() 函數(shù)。

# 導入 turtle 庫
import turtle
# 創(chuàng)建小烏龜對象
my_turtle = turtle.Turtle()
# 創(chuàng)建用戶繪制圖案的窗口
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 模塊繪制分形樹。分形樹和遞歸有許多的共同點，是數(shù)學中的一個概念，無論放大多少倍觀察分形圖，總能看到相同的基本形狀。

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

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數(shù)據(jù)結構之遞歸可視化詳解的文章就介紹到這了,更多相關Python遞歸可視化內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論