1.學(xué)習(xí)目標(biāo)

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

通過本節(jié)學(xué)習(xí)，應(yīng)掌握以下內(nèi)容：

提高對(duì)遞歸的理解

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

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

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

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

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()

當(dāng)程序運(yùn)行到第 10 行時(shí)。第一次調(diào)用 fibo() 函數(shù)，會(huì)為 fibo() 函數(shù)調(diào)用創(chuàng)建一條新的活動(dòng)記錄，此時(shí)在運(yùn)行時(shí)棧上具有 3 條活動(dòng)記錄。然后 Python 解釋器跳轉(zhuǎn)到第 2 行，其中 n 指向數(shù)字 4，如下圖所示。n 不等于 0，因此跳轉(zhuǎn)到第 5 行，其中包含一個(gè)對(duì) fibo() 的函數(shù)調(diào)用，這將在運(yùn)行時(shí)堆棧上創(chuàng)建另一個(gè)活動(dòng)記錄。重復(fù)上述過程，直到 n=0。

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

當(dāng)函數(shù)執(zhí)行到 n=0 時(shí)，fibo() 函數(shù)返回了它的第一個(gè)值，它將 1 返回到上一個(gè)函數(shù)調(diào)用。如下圖所示，從運(yùn)行時(shí)堆棧中彈出 n=0 時(shí)函數(shù)調(diào)用的活動(dòng)記錄(通過將圖中活動(dòng)記錄的變?yōu)榛疑珌肀硎?。當(dāng)函數(shù)返回時(shí)，活動(dòng)記錄的空間被回收以供以后使用。堆上的陰影對(duì)象 0 也被垃圾收集器回收，因?yàn)椴辉儆兄赶蛩囊谩?/p>

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

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

3.遞歸可視化

本節(jié)將利用 turtle 庫遞歸的繪制圖案，提高對(duì)遞歸過程的認(rèn)識(shí)。

3.1 turtle 庫簡(jiǎn)介

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

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

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

3.1 遞歸繪圖

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

# 導(dǎo)入 turtle 庫
import turtle
# 創(chuàng)建小烏龜對(duì)象
my_turtle = turtle.Turtle()
# 創(chuàng)建用戶繪制圖案的窗口
window = my_turtle.getscreen()

def draw(turtle, distance):
? ? if distance > 0:
? ? ? ? # 小烏龜向前繪制 distance 個(gè)單位距離
? ? ? ? turtle.forward(distance)
? ? ? ? # 然后左轉(zhuǎn) 30 度
? ? ? ? turtle.left(30)
? ? ? ? draw(turtle, distance-6)
draw(my_turtle, 200)
window.exitonclick()

接下來，我們使用 turtle 模塊繪制分形樹。分形樹和遞歸有許多的共同點(diǎn)，是數(shù)學(xué)中的一個(gè)概念，無論放大多少倍觀察分形圖，總能看到相同的基本形狀。

如果我們定義樹為包含向左生長(zhǎng)的子樹和向右生長(zhǎng)的子樹的話，就可以根據(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()

到此這篇關(guān)于Python數(shù)據(jù)結(jié)構(gòu)之遞歸可視化詳解的文章就介紹到這了,更多相關(guān)Python遞歸可視化內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論