本篇全部用來介紹「遞迴函式」（多寫為「遞迴」，也作「遞回」、「遞歸」）。遞迴 (recursive) 函式的特徵是函式「呼叫自己」，又分為直接遞迴與間接遞迴。遞迴可說是解決問題的利器，非常多有名的演算法如快速排序 (quicksort), 二分搜尋 (binary search), 以及樹 (tree), 圖 (graph) 等資料結構的操作都仰賴它。 除本文提供的範例之外，讀者也可以參考這篇文章的第四段。 以下就用階乘 (factorial) 的計算為例，展示如何寫出遞迴函式： 註：階乘即連續整數的乘積，數學上符號用 "!", n! = n*(n-1)*(n-2)*...*2*1, 但是 0! = 1! = 1. 二個版本都算出一樣答案 120. 迴圈做法很直覺地從 1 開始，乘以 2 再乘以 3, 一直乘到 $n. 然而遞迴的想法是，$n 階乘就是 $n 乘以 $n-1 階乘，於是 $n-1 階乘正好為同樣「階乘」這個函式代入 $n-1 的答案，因此可以呼叫自己。 相形之下，遞迴函式寫法比迴圈少很多程式碼。遞迴函式的實作分為二部份，邊界條件與遞迴關係式。「階乘」的遞迴關係為 $n 階乘等於 $n 乘以 $n-1 階乘，但如果永無止盡的遞迴下去，等於 $n 乘以 $n-1 乘以 $n-2 階乘，再展開到 $n-3 階乘……就跟無窮迴圈一樣跑不完，因此需要邊界條件使其停止遞迴。通常邊界條件是一小組已知的答案，且任何輸入 $n 都會展開到它，如階乘選擇 0 與 1 階乘都是 1, 2 以上的階乘都會因為代入 $n-1 逐漸把輸入變小到 1 而終止遞迴。 以下詳細剖析 Factorial_Recursive(5) 執行的過程。當呼叫函式，不但引起執行順序改變，還會改變記憶體中的堆疊 (stack). 「堆疊」是一個想像的資料結構，好像布丁桶一樣，光碟從下面逐漸疊上去，但是要取出資料時只能先移除上面的光碟才能拿到下面的，這特性稱為「後勁先出」。光碟就是堆疊裡的每筆記錄 (record), 遇到函式呼叫就會朝堆疊推入一個新的記錄，記錄裡保有函式當下使用的參數與區域變數，以及函式結束時要返回的位置。關於「堆疊」更詳細的觀念可查閱計算機概論、資料結構及程式語言設計的書籍。
當執行到 Factorial_Recursive(5) 時，堆疊裡新增了第一個記錄，寫著 $n = 5 及返回位置，如下：
[Factorial_Recursive: $n=5, 返回位置在倒數第二行 MsgBox]它將執行到 Return 5 * Factorial_Recursive(4), 讓堆疊變成：
[Factorial_Recursive: $n=4, 返回位置在 Factorial_Recursive 最後一行] Factorial_Recursive(5) 一直都是未執行完的狀態，現在 Factorial_Recursive(4) 也停在 Return 4 * Factorial_Recursive(3) 讓堆疊變成：
[Factorial_Recursive: $n=3, 返回位置在 Factorial_Recursive 最後一行]注意後來插入的兩筆記錄，返回位置一樣，因為都在那個地方遞迴呼叫自己的。類推下去，堆疊最深時內容是： [Factorial_Recursive: $n=1, 返回位置在 Factorial_Recursive 最後一行] Factorial_Recursive(1) 不再遞迴，執行 Return 1 而結束，堆疊刪去最上層，並返回 Factorial_Recursive(2) 時卡住的 Return 2 * Factorial_Recursive(1) 這邊，後面 Factorial_Recursive(1) 已經計算完成答案是 1, 所以變 Return 2 * 1 然後將 2 回傳並結束執行。
類推下去 Factorial_Recursive(3) 將 Return 3 * 2, Factorial_Recursive(4) 將 Return 4 * 6, Factorial_Recursive(5) 將 Return 5 * 24, 於是返回 MsgBox 那行時答案就是 120.
遞迴函式執行的過程一定伴隨大量頻繁堆疊的消長，因此相當耗用記憶體資源，如果無窮遞迴則最後將因記憶體耗盡而結束。迴圈實作階乘看起來雖然多幾行程式碼，但執行過程簡單又不耗用記憶體，因此也不是所有事情都要靠程式碼簡單的遞迴解決，但是有許多演算法需要堆疊的配合，以遞迴實作的成本遠低於迴圈。
剛才只展示「直接遞迴」，「間接遞迴」就是在函式執行過程中呼叫了別的函式中有呼叫回自己，即函式 A 呼叫 B, B 又呼叫 A. 因為比較少用，本文不再舉例說明。
第二個範例展示使用遞迴編寫二分搜尋。假設一個陣列已被排序成由小而大，將想要找的值與陣列內其中一個元素比較，要是陣列元素較大，那陣列裡其他位置更後面的元素一定也比想找的值大，因此只要往陣列的另一個方向找就可以。每次比較都可以排除掉範圍內一半的元素，因而稱為「二分」搜尋。 這個範例的結構比剛才複雜許多，遞迴關係式有兩條，邊界條件的位置也不明顯。二分搜尋停止的狀況其實直覺上有三種，找到答案、沒找到答案跟呼叫者故意亂給參數。 二分搜尋的四個參數分別為要找的值，稱為「鍵」 (key), 被找的陣列、被找範圍的下界跟上界，也就是要找的範圍在 $low 到 $high, $low 最小可以 0, $high 最大可以 UBound($array)-1, $high 的最大值就是陣列裡最後一個元素的索引位置。
一開始我們用「默認參數」的技巧，讓呼叫者可以不必親自指定範圍，因為一般而言「搜尋」是對於整個陣列的。函式首先過濾 Default 把它改成剛才提到的 $low 最小及 $high 最大，這是預設的搜尋範圍。
確定好搜尋範圍後，先挑出參數不合理的狀況，就是 $low 比 $high 大。這裏使用單行 If...Then 分支，因為符合條件就 Return 跳出函式，其餘部分可以不必 Else 包住。這種寫法可以視為「過濾」不合理的狀況使之不繼續執行。
接著從陣列中央下手，計算 $low, $high 的平均 $mid, 然後看看陣列在中間 $mid 位置的值與 $key 的關係，決定要找哪個半邊或找到答案了。算平均時要去掉小數 0.5 的部份，所以用 Floor 內建函式辦到無條件捨去。
$key 與陣列 $mid 位置的元素比較，$key 較小找左半，較大找右半，要是一樣表示 $mid 就是我們要的答案位置。找左半的時候因為 $mid 已經確定不是答案，所以範圍填入 $low 到 $mid-1; 找右半也因 $mid 位置確定非答案所以從 $mid+1 到 $high.
至此，已經考慮了遞迴關係式和兩種邊界條件，可是「找不到」這種狀況會如何？尋找過程中 $low, $high 不斷靠近，最後將變城 $low 等於 $high, 也就是被找的範圍剩下一個元素，此時又不是正確答案而傳回 $mid, 一定會再「往左」或「往右」找，於是造成不合理輸入，在 Return -1 被過濾掉而整個結束。
這個範例與 10-1 不同處在於，它遞迴的次數不一定，不像範例 10-1 輸入 $n 一定會遞迴 $n 次。有興趣的讀者可以探索演算法 (algorithm) 的相關內容，二分搜尋的最差狀況是遞迴 log n 次，這個 n 是被找的陣列長度，與資料內容和鍵無關，log 是數學上的「對數」。
回 · 我的 AutoIt 學習筆記 這一篇文章封面 |
| 本站公告：〔您越需要我們，我們就越有創意〕 | 本站說明書：〔發現故鄉還有改進的地方，請來信告訴原丁們〕 |
| 觀察應用學習點數 ：〔咱的故鄉有您的參與，會使我們有更大的發揮空間，展現更豐富精彩的學習畫面〕 | 〔期待藉由無障礙網頁設計，能讓視障小朋友更愛看書、更愛寫作且更愛學習〕：盲用電腦「心得分享」 |