關於此實驗
樹由一段樹幹和上方的兩棵小樹組成。這一句話就是一個完整的程式：一個繪製樹枝後再呼叫自身兩次的函式。遞迴能用簡短的規則產生豐富的圖像。觀察一棵樹、一個謝爾賓斯基三角形和一片科赫雪花如何隨著一次次呼叫逐漸建構，追蹤呼叫堆疊的增長與縮小，並數數隨著深度增加，呼叫次數會以多快的速度激增。
學習目標
- 辨識遞迴函式的基本情況和遞迴情況
- 追蹤遞迴呼叫執行與返回的順序
- 說明呼叫堆疊中存放的內容，以及堆疊的深度為何重要
- 計算給定深度對應的呼叫次數，例如二元樹中的 2^(n+1) − 1
- 描述自我相似性，並計算一個簡單的分形維度
使用方法
- 1選擇深度為 3 的樹，慢慢觀察呼叫過程。左分支和右分支中，哪一個先繪製？為什麼？
- 2在堆疊達到最深處時暫停。堆疊中的每個框架代表什麼？與深度相比，框架的數量是多少？
- 3填寫樹的深度與呼叫次數對照表。找出規律，並在深度為 10 時進行驗證。
- 4更改分支角度和長度比例。哪些設定會使分支重疊？
- 5切換到謝爾賓斯基三角形。程式碼中的基本情況在哪裡？深度為 5 時會繪製多少個三角形？
- 6建立深度為 5 的科赫雪花。利用讀數說明周長如何不斷增長，而面積仍然有限。
模型
假設
- 這些呼叫依照程式中的順序一次執行一個，採用深度優先方式，與一般程式語言執行它們的方式完全相同。
- 偽程式碼將位置和方向作為參數傳遞，因此呼叫返回後無需還原海龜的狀態。
- 樹的分形維數 log 2 / log(1/r) 只描述枝梢，而且前提是樹枝彼此沒有重疊。
- 為確保逐步重播仍能快速執行，我們限制了最大深度：樹為 12，三角形為 7，雪花為 6。
在課堂上試試這個實驗
- Q1如果樹函式沒有基本情況，會發生什麼事？
- Q2深度為 4 時，謝爾賓斯基函式會呼叫幾次？請用一個和來說明答案。
- Q3儘管進行了數千次呼叫，為什麼呼叫堆疊的深度始終不會超過遞迴深度加一？
- Q4撰寫一個計算 n! 的遞迴函式，並指出它的基本情況。
- Q5測量英國海岸線時，使用的尺越短，測得的海岸線就越長。科赫雪花如何解釋這種現象？
常見問題
遞迴比迴圈慢嗎？
每次呼叫都會為堆疊框架消耗少量時間和記憶體，因此迴圈通常會稍微快一些。但對於樹、巢狀資料夾或語法解析等分支結構，遞迴撰寫起來簡單得多，而且任何遞迴都可以改寫成自行明確維護堆疊的形式。
什麼是堆疊溢位？
每個尚未完成的呼叫都會在呼叫堆疊中保留一個堆疊框架。如果遞迴太深，例如始終無法到達基本情況，堆疊記憶體就會耗盡，程式會因堆疊溢位錯誤而當機。
自然界中的分形有哪些？
蕨類植物、羅馬花椰菜、河川網絡、閃電、血管，以及肺部呈分支狀的氣道，在多個尺度上都近似具有自相似性。因此，電腦圖形學會使用遞迴規則來生成它們。