網頁標題: 10 使用者自定義函式 (3): 遞迴

Warning: fopen(/home/crazy/www/cmsb/bcj/has_read.php): failed to open stream: Permission denied in /home/crazy/www/compose/reading.php on line 2070

Warning: fputs() expects parameter 1 to be resource, bool given in /home/crazy/www/compose/reading.php on line 2072

Warning: fclose() expects parameter 1 to be resource, bool given in /home/crazy/www/compose/reading.php on line 2073
 
﹗﹗﹗觀看留言:此文章已經有2則留言 ﹗﹗﹗


 本篇全部用來介紹「遞迴函式」(多寫為「遞迴」,也作「遞回」、「遞歸」)。遞迴 (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: $n=5, 返回位置在倒數第二行 MsgBox]
 Factorial_Recursive(5) 一直都是未執行完的狀態,現在 Factorial_Recursive(4) 也停在 Return 4 * Factorial_Recursive(3) 讓堆疊變成:

[Factorial_Recursive: $n=3, 返回位置在 Factorial_Recursive 最後一行]
[Factorial_Recursive: $n=4, 返回位置在 Factorial_Recursive 最後一行]
[Factorial_Recursive: $n=5, 返回位置在倒數第二行 MsgBox]
 注意後來插入的兩筆記錄,返回位置一樣,因為都在那個地方遞迴呼叫自己的。類推下去,堆疊最深時內容是:

[Factorial_Recursive: $n=1, 返回位置在 Factorial_Recursive 最後一行]
[Factorial_Recursive: $n=2, 返回位置在 Factorial_Recursive 最後一行]
[Factorial_Recursive: $n=3, 返回位置在 Factorial_Recursive 最後一行]
[Factorial_Recursive: $n=4, 返回位置在 Factorial_Recursive 最後一行]
[Factorial_Recursive: $n=5, 返回位置在倒數第二行 MsgBox]
 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 學習筆記 這一篇文章封面


本文張貼者:Bo-Cheng Jhan〔張貼時間:民國105年5月17日(星期二)18點07分〕

部落格首頁


學習的故鄉首頁
本站公告:〔您越需要我們,我們就越有創意〕 本站說明書:〔發現故鄉還有改進的地方,請來信告訴原丁們〕
觀察應用學習點數 :〔咱的故鄉有您的參與,會使我們有更大的發揮空間,展現更豐富精彩的學習畫面〕 〔期待藉由無障礙網頁設計,能讓視障小朋友更愛看書、更愛寫作且更愛學習〕:盲用電腦「心得分享」
〔為了讓我們有乾淨的學習環境,請勿任意在本站散播商業廣告與不合法文件或聯結〕:本站宣示