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