維基百科

遞歸 (電腦科學)

描述入面會出現對所描述嘅事物本身嘅提及

遞歸（粵拼：dai6 gwai1；英文：recursion）喺程式編寫上，如果係講緊子程式嘅定義，狹義上係指子程式嘅定義會直接用到[註 1]自己，廣義上就指子程式會直接或者間接用到自己[1]:41；如果講子程式嘅執行，指嘅係指子程式會直接或者間接啟動[註 2]自己[1]:121。遞歸可以用來將一條問題分做條問題「細啲嘅版本」噉嚟解[2]。

好似樹狀呢啲形狀，可以用遞歸演算法嚟畫。

狹義上子程式嘅遞歸，原則上同邏輯上講嗰種遞歸上係同一樣嘢，都係 ｢用自己定義自己｣，但係子程式嘅啟動牽涉有限資源同副作用等等；廣義嘅遞歸，或者執行嘅時候講嘅遞歸，都可以視為狹義嘅遞歸喺特定語境之下嘅引伸義。

喺程式語言嘅理論上，遞歸有兩種特別情形：如果喺實際執行嘅時候，一個子程式嘅啟動（activation）最多只會再啟動自己一次，呢種叫 linear recursion（線性遞歸）[1]:42。如果一個子程式一係唔啟動自己，一係就喺輸出（return）嘅時候先啟動自己，呢種叫尾遞歸（tail recursion）[1]:43；喺翻譯嘅時候，尾遞歸係可以有方法令佢實際上變成唔涉及遞歸嘅其他嘅流程控制[1]:143。

基本諗頭

編輯
内文：子程式同遞歸
睇埋：控制流程同堆疊

遞歸最重要嘅特徵，係指一個子程式會「用到自己」或者「𠹭call自己」。呢種做法可以當係分治演算法[e 1]嘅一類，將一個大嘅問題「揼散」做若干個細嘅問題[3]。舉例說明，想像依家要教電腦計階乘嘅數，可以想像以下嘅虛擬碼[2][4]：

呢個子程式叫 factorial(x)
如果 x == 0：
Output 係 1
否則：
Output 係 x 乘以 factorial(x-1)

——factorial 呢個子程式，會「用返自己」。假如 input x 數值係 5，行呢個程式就會好似噉：

factorial(x) 行嗰陣嘅情況
  1. 個程式行 factorial(x-1)，呢個 factorial 以 4 做 input；
  2. 個程式行 factorial(x-1)，呢個 factorial 以 3 做 input；
  3. 個程式行 factorial(x-1)，呢個 factorial 以 2 做 input；
  4. 個程式行 factorial(x-1)，呢個 factorial 以 1 做 input；
  5. 個程式行 factorial(x-1)，呢個 factorial 以 0 做 input；
  6. 因為 x 數值去到 0，個子程式出 1；
  7. return x * factorial(x-1)，factorial(0) 出 1，1 * 1 出 1；
  8. return x * factorial(x-1)，factorial(1) 出 1，2 * 1 出 2；
  9. return x * factorial(x-1)，factorial(2) 出 2，3 * 2 出 6；
  10. return x * factorial(x-1)，factorial(3) 出 6，4 * 6 出 24；
  11. return x * factorial(x-1)，factorial(4) 出 24，5 * 24 出 120；
  12. 最後成個程式出 120 做答案。

如是者，個程式就計到階乘  。

兩大部份

編輯
睇埋：無限迴圈

一個用咗遞歸嘅子程式，有兩大組成部份：基本個案同遞歸個案[5]:p 28 - 32。

  • 基本個案[e 2]會「即刻畀 output」，唔會引致任何進一步嘅遞歸，電腦一𠹭佢，就會得到 output。好似係計階乘嗰個例子噉，佢個基本個案就係 如果 x == 0：output 係 1 嗰一截。用親遞歸嘅子程式都梗要有個基本個案，唔係嘅話個子程式就會進入無限迴圈。
  • 遞歸個案[e 3]會有進一步遞歸，但係每一次遞歸個問題都會「細咗」或者「簡單咗」，而且會愈嚟愈接近基本個案。喺計階乘嘅例子裡便，佢個遞歸個案係 否則：output 係 x 乘以 factorial(x-1) [註 3]嗰截——呢段嘢每行一次，個問題都會愈嚟愈接近基本個案。

有啲人會將上述過程想像成「一個堆堆裝住未解嘅遞歸個案，遞歸個案一個個噉堆，堆到去到基本個案，再一個個噉解咗佢」[6]。

 
堆疊嘅圖解；堆疊有一舊舊數據，處理起上嚟係「後入先出」（LIFO）嘅，喺呢方面遞歸好相似，個子程式一路行，行到去基本個案度，然後越接近基本個案嘅會「解決咗先」。
堆疊嘅圖解；堆疊有一舊舊數據，處理起上嚟係「後入先出」（LIFO）嘅，喺呢方面遞歸好相似，個子程式一路行，行到去基本個案度，然後越接近基本個案嘅會「解決咗先」。 

遞歸種類

編輯

「遞歸嘅威力在於佢能夠用有限嘅陳述式，定義無限咁多件物件。同一道理，有限嘅遞歸程式可以描述數量無限嘅運算，而且就算個程式冇講明要重複都得。」

——尼克勞斯·維爾特[7]

單一定多重

編輯
 
費氏數列示意圖：喺二維空間，如圖所示噉用正方形排長方形出嚟，如果第一個正方形嘅邊長係 1，順序擺落去嘅每個正方形嘅邊長一定會形成費氏數列。

遞歸可以分做單一同多重兩種。呢個分類係講緊個子程式會𠹭call佢自己𠹭幾多次，單一遞歸比較簡單，個子程式嘅定義只會𠹭自己一次，而多重遞歸就比較複雜，個子程式嘅定義會𠹭自己超過一次。

例如費氏數列[e 4]就可以用多重遞歸嚟計[8]。費氏數列係一個好出名嘅數列，頭兩個數係 0 同 1，跟住落嚟嘅數就係之前兩個數加埋嘅和，假設 n 係整數，數學上就可以噉定義：

 

將數學定義直接譯做演算法，就會得出類似下面嘅虛擬碼[8][註 4]：

子程式 fib ( n )：
如果 n ≤ 1：
答案係 n
否則
答案係 fib (n - 2) + fib (n - 1)

最後一行有 fib (n - 2) 同 fib (n - 1) 兩個呼叫（call），兩個呼叫都會執行，所以噉做法係多重遞歸。

一個程式用咗多重遞歸，好易會出現運算複雜度過高嘅問題。例如上面嗰段演算法，個子程式每行一次，都會叫自己兩次，然後嗰兩個呼叫就會各自產生多兩個呼叫變成四個呼叫——兩重遞歸嘅運算複雜度會傾向係  （即係同   成正比），而如果段演算法有三重遞歸，運算複雜度就會傾向  ... 如此類推。無論講時間複雜度定空間複雜度，呢種情況都係唔理想嘅[9]。因此，好多編程工作者都主張多重遞歸呢家嘢可免則免。

直接定間接

編輯
内文：相互遞歸
睇埋：有限狀態機

遞歸又可以分做直接同間接。直接遞歸係話個子程式會直接呼叫自己，而間接遞歸，又叫相互遞歸[e 5]，就可以係個子程式呼叫另外一個子程式，而另外嗰個子程式又會呼叫返原先嗰個子程式[4]。

相互遞歸都有唔少用途。有限狀態機[e 6]就可以透過相互遞歸演算法嚟實現。一部有限狀態機會有若干個「狀態」，每個狀態涉及嘅行為都唔同。例如電子遊戲入便嗰啲 AI 技術就成日會用到有限狀態機，想像而家要製作一隻動作遊戲，遊戲入便嘅 AI 敵人有若干個狀態，就可以用好似以下噉嘅虛擬碼，嚟教電腦點樣控制呢啲敵人：

子程式 ceon lo () # 巡邏
如果 見到玩家角色，就 zeoi bou ()
否則 繼續做巡邏要做嘅嘢。
子程式 zeoi bou () # 追捕
如果 玩家角色進入射程，就 gung gik ()
如果 玩家角色離開視線，就 ceon lo ()
否則 繼續做追捕要做嘅嘢。
子程式 gung gik () # 攻擊
如果 玩家角色離開射程，就 zeoi bou ()
否則 繼續做攻擊要做嘅嘢。

就算到咗廿一世紀初，呢種控制遊戲敵人嘅技術都仲好多人用[10][11]。

係咪擺尾

編輯
内文：尾遞歸

尾遞歸[e 7]係指叫部電腦遞歸嗰一句嘢，係成個子程式最後嗰句陳述式：一旦行咗嗰句嘢，個子程式就算係成個行晒；而且部電腦冇需要紀錄住打前嗰個狀態。例如以下呢個子程式[12]

呢個子程式叫 print_saai(n) # print 晒
如果 n < 0：
return
否則：
print(n)
print_saai(n-1) # 成個子程式最後一句係叫部電腦遞歸。

而以下個子程式，就噉望落似係尾遞歸，但其實唔係[12]：

呢個子程式叫 fac(x)
如果 x == 0：
return 1
否則：
return 係 x 乘以 fac(x-1)

——想像而家個子程式行咗幾次，去到 x-1 = 0 嘅地步。部機跟住要做 fac(0)，出 1，然後佢要再計 1*1 嘅數，先至可以算係搞掂 fac(1)。喺部機行緊 fac(0) 嗰段期間，部機要記住「fac(1) 個 x 係幾多」呢一項資訊。因此，呢個子程式唔算係尾遞歸。一個子程式用咗尾遞歸，表示每行一個新嘅遞歸呼叫，之前嗰個呼叫就算係解決咗（部機唔使再記住嗰個呼叫嘅嘢），而呢點可以令到個程式用起記憶體上嚟更有效率。

遞歸實行

編輯

包裝函式

編輯
内文：包裝函式

包裝函式[e 8]係指一個「包裝住」另外一個子程式嘅子程式。如果呢種程序攞嚟同一個遞歸程序一齊用嘅話，通常會係類似噉：

Def 遞歸程序 (n)
遞歸程序要做嘅嘢...
Def 包裝程序 (n)
包裝程序要行嘅運算...
Call 個遞歸程序
然後主程式會 call 個包裝程序

噉嘅話主程式行起上嚟，就會行咗個包裝程序先，然後再開始進入遞歸嘅狀態。

「包裝程序要行嘅運算」可以係好多有用嘅功能，例如係事前處理啲 input 嘅數值[註 5]或者係檢查吓啲 input 係咪合乎某啲條件（例如想確保入落去遞歸程序嘅數細過某啲指定數值）呀噉[13]。呢種做法被指有好多好處——將事前處理等嘅嘢分離咗出嚟，交畀包裝程序處理，就可以達到模塊化[e 9]嘅效果，令到啲源碼更易打理[14]。

出名應用

編輯
睇埋：樹狀數據同碎形

喺編程上，遞歸可以用嚟解決一啲可以揼散做一大柞細問題嘅問題，而且當中每一個細問題都屬同一個類型。

對比疊代

編輯
睇埋：疊代

同遞歸一樣，疊代[e 10]程序都係一種用嚟重複某啲操作嘅技巧。

理論分析

編輯
睇埋：分治演算法

常見錯誤

編輯

睇埋

編輯

文獻

編輯
  • Bible, P. W., & Moser, L. (2023). An Open Guide to Data Structures and Algorithms. Palni Open Press. 2. Recursion
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press. 4.4 The recursion-tree method for solving recurrences
  • Dijkstra, Edsger W. (1960). "Recursive Programming". Numerische Mathematik. 2 (1): 312–318. doi:10.1007/BF01386232.

參考

編輯

註釋：

  1. ↑ 理論上跟數學講 apply，編程通常講 call
  2. ↑ 理論上講 activate，編程通常叫 call
  3. ↑ 嚴格嚟講，呢度個否則係不必要嘅。
  4. ↑ 呢套演算法查實有唔少問題，例如計 fib (n - 2) 同計 fib (n - 1) 都要計 fib (n - 3)，但係喺以下嘅演算法當中，計 fib (n - 3) 呢樣嘢行咗兩次，嘥時間資源。
  5. ↑ 可以睇睇事前數據處理。

篇文用咗嘅行話詞彙，英文名如下：

  1. ↑ divide-and-conquer
  2. ↑ base case
  3. ↑ recursive case
  4. ↑ Fibonacci sequence
  5. ↑ mutual recursion
  6. ↑ finite state machine，FSM
  7. ↑ tail recursion
  8. ↑ wrapper function
  9. ↑ modularized
  10. ↑ iteration

篇文引用咗以下呢啲文獻同網頁：

  1. ↑ 1.0 1.1 1.2 1.3 1.4 Sethi, Ravi (1990) [1989]. Programming Languages: Concepts and Constructs. Reading, MA: Addison-Wesley. ISBN 0-201-10365-6.
  2. ↑ 2.0 2.1 Jaimini, Vaibhav. "Recursion and Backtracking".
  3. ↑ Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
  4. ↑ 4.0 4.1 Reading 14: Recursion，麻省理工學院
  5. ↑ Bible, P. W., & Moser, L. (2023). An Open Guide to Data Structures and Algorithms. Palni Open Press.
  6. ↑ How Recursion Works — Explained with Flowcharts and a Video. freeCodeCamp.
  7. ↑ Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126. "The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."
  8. ↑ 8.0 8.1 Understanding Multiple Recursion Calls: Unraveling the Fibonacci Problem. Medium.
  9. ↑ Multiple Recursive Calls: Fibonacci Sequence, Part 1.
  10. ↑ Millington, I., & Funge, J. (2009). Artificial Intelligence for Games. CRC Press.
  11. ↑ Rabin, S. (2006). AI Game Programming Wisdom 3 (Game Development Series). Charles River Media, Inc..
  12. ↑ 12.0 12.1 What is Tail Recursion. GeeksForGeeks.
  13. ↑ The Advantages of Using Wrappers in Python. Medium.
  14. ↑ Exploring JavaScript Function Wrappers: A Comprehensive Guide. CloudDevs. 3.2. Modularity

拎

編輯
 
維基同享有多媒體嘅嘢：
遞歸演算法
由「https://zh-yue.wikipedia.org/w/index.php?title=遞歸_(電腦科學)&oldid=2176548」收