遞歸 (電腦科學)

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

遞歸粵拼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]

遞歸種類

編輯

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

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

單一定多重

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

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

例如費氏數列[e 4]就可以用多重遞歸嚟計[8]。費氏數列係一個好出名嘅數列,頭兩個數係 01,跟住落嚟嘅數就係之前兩個數加埋嘅和,假設 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