【演算】遞迴函式 - Recursive Function

　　所謂的遞迴（recursion），簡單來說就是「函式（function）不斷呼叫自身」的一種程式撰寫法。遞迴的意義，在於把一個問題切割成相同性質的較小問題來解決。而為了防止程式無窮盡的遞迴下去，我們還必須為所寫出來的遞迴函式設定一個終止條件（termination condition）。

　　遞迴的原理，是利用函式本身的堆疊（stack）性質－－後進先出（last in, first out，LIFO）來達成的。說得簡單一點，就是當某個函式呼叫另一個函式時，其會先執行完被呼叫的函式，才繼續執行自身的函式內容。



　　讓我們舉一個常見的例子來解釋：階乘（factorial）。

　　在數學上的定義中，對於一個非負整數 n，其階乘代表的是所有小於或等於 n 的正整數乘積，記作 n!。即 n! = 1 × 2 × 3 × ... × n。若我們規定 0! = 1，則可以將之改寫成：對於所有非負整數 n，(n + 1)! = (n + 1) × n!。

　　於是，我們便可以利用程式寫出計算階乘的遞迴函式。以下為其虛擬碼：

Function factorial(Integer n)
    If n = 0 then
        Return 1
    Else
        Return n × factorial(n - 1)
End

　　在這裡，我們相當於將原始的問題 n! 看作是 n × (n - 1)! 這個較小的問題。也就是得知 (n - 1)! 的值，就可以求得 n! 的解。同樣的，又可以將 (n - 1)! 看作是 (n - 1) × (n - 2)!、將 (n - 2)! 看作是 (n - 2) × (n - 3)!、......。

　　舉例來說，若是我們需要利用程式求出 6! 的值。則在我們呼叫 factorial(6) 時，為了得出結果，亦須求出 factorial(5) 的值。而為了得出 factorial(5) 的結果，我們亦須求出 factorial(4) 的值......。一直不斷遞迴下去，直到達到終止條件：n = 0 為止。

　　實際運作的結果，就如下圖所示意的（藍箭頭代表呼叫，紅箭頭代表回傳）：





　　除此之外，遞迴還可以解決相當多其他的問題。例如斐波那契數列（fibonacci sequence）、老鼠走迷宮（mouse in a maze）、以及河內塔（tower of hanoi）等等，這裡我就不加贅述了。



　　雖然利用程式的遞迴解法較為直觀，但是不斷堆疊函式的結果，極有可能浪費了過多的記憶體空間。其實，遞迴的程式多半都能藉由迴圈的方式替代，只是程式也可能會因此變得複雜難懂。至於實際上要使用何者，就看你怎麼選擇囉。