互遞歸
互遞歸是數學與計算機科學中一種遞歸，指兩個數學或計算機對象如函數或數據類型互相定義。[1]互遞歸在函數程式語言或某些問題域中非常常見，如遞歸下降分析器，其中數據類型是自然地互相遞歸定義的。
例子
[編輯]數據類型
[編輯]採取互遞歸定義的最重要的基本數據類型是樹。這可以用於定義森林（樹的列表）:
f: [t[1], ..., t[k]] t: v f
森林f由一棵樹的列表組成，同時一棵樹t由一對：值v與森林f (子樹)構成。這種定義是精緻的，易於工作的抽象性（如用於證明關於樹的屬性的定理），因為它用簡單術語表示一棵樹：一個類型的列表，兩個類型組成的一對。而且它匹配許多關於樹的算法，這些對值做一些事，對子樹做另外一些事。
這種互遞歸定義可以轉換為單個遞歸，這是通過森林定義內部化：
t: v [t[1], ..., t[k]]
一顆樹t包含一對：值v與子樹的列表。這個定義更緊緻，但是更難以處理：一棵樹是一種類型的值與另一種類型的列表組成的一對，這要求解析開以證明結果。
在Standard ML，樹與森林可互遞歸定義如下，允許空樹：[2]
datatype 'a tree = Empty | Node of 'a * 'a forest
and 'a forest = Nil | Cons of 'a tree * 'a forest
計算機函數
[編輯]如同在遞歸數據類型上的算法可以自然由遞歸函數給出，互遞歸數據結構上的算法可自然地由互遞歸函數給出。常見例子包括樹與遞歸下降解析器。如同直接遞歸，對遞歸深度很大或者是無窮的情形尾調用優化是必須的，如使用互遞歸的多任務。注意一般的尾調用優化比作為特例情況的尾遞歸調用優化更難實現，因此有效實現互尾遞歸未被很多語言考慮。對Pascal語言要求先聲明後使用，互遞歸要求前向聲明。
如同直接遞歸函數，包裝函數（wrapper function）對互遞歸函數是有用的作為包裝函數的作用域內的嵌套函數（如果支持的話）。這對跨多個函數共享狀態而不直接傳遞參數特別有用。
基本例子
[編輯]一個例子用於確定奇偶數。[3] C語言：
bool is_even(unsigned int n) {
if (n == 0)
return true;
else
return is_odd(n - 1);
}
bool is_odd(unsigned int n) {
if (n == 0)
return false;
else
return is_even(n - 1);
}
這套函數是基於對問題4是偶數?等價於3是奇數?，依次等價於2是偶數?，直到0. 這個例子是相互單遞歸，很容易改寫為迭代。這個例子中的互遞歸是尾調用，尾調用優化是必須的以能在常量大小棧空間完成計算。C語言這要求O(n)棧空間，除非重寫用跳轉代替調用。[4]
Python語言實現樹的例子:
def f_tree(tree):
f_value(tree.value)
f_forest(tree.children)
def f_forest(forest):
for tree in forest:
f_tree(tree)
高級例子
[編輯]遞歸下降解析器可以自然地實現為每個產生式規則對應一個函數，就可以是互遞歸、多遞歸，因為產生式規則一般要組合多個部分。
互遞歸也可以實現有限狀態機，每個函數表示一個狀態，這要求尾遞歸優化因為狀態變遷可能是非常大或無限的。互遞歸可用於合作多任務，以代替協程。
有些算法自然地分成兩個階段，如minimax算法，每個階段可以用一個函數實現。
數學函數
[編輯]數學上，Hofstadter Female and Male sequences是一對整數序列用互遞歸方式定義的例子。
分形可用遞歸函數計算。有時用互遞歸計算更為精緻，如Sierpiński curve。
流行性
[編輯]互遞歸在函數程式語言風格中是常用的，如Lisp, Scheme, ML語言等。Prolog中互遞歸是不可避免。
If you have two mutually-recursive functions that both alter the state of an object, try to move almost all the functionality into just one of the functions. Otherwise you will probably end up duplicating code.
術語
[編輯]轉換為直接遞歸
[編輯]數學上，一套互遞歸函數是原始遞歸函數, 可通過course-of-values recursion證明,[6] 構造單個函數F依次列出單個遞歸函數的值: ，重寫互遞歸為原始遞歸。
任何兩個過程之間的互遞歸可以轉換為直接遞歸，這通過把一個過程內聯至另一個過程實現。 [7]
任何數量的互遞歸過程可以合併為單一過程，這通過標籤聯合 (一種代數數據類型)表示選擇過程與它的參數。這可以看作defunctionalization的有限應用.[8]
參見
[編輯]參考文獻
[編輯]- ^ Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes,Cristóbal Pareja-Flores (2002), 'A Gentle Introduction to Mutual Recursion', Proceedings of the 13th annual conference on Innovation and technology in computer science education, June 30–July 2, 2008, Madrid, Spain.
- ^ Harper 2000，"Date Types".
- ^ Hutton 2007，6.5 Mutual recursion, pp. 53–55.
- ^ "Mutual Tail-Recursion （頁面存檔備份，存於網際網路檔案館）" and "Tail-Recursive Functions （頁面存檔備份，存於網際網路檔案館）", A Tutorial on Programming Features in ATS （頁面存檔備份，存於網際網路檔案館）, Hongwei Xi, 2010
- ^ Solving Every Sudoku Puzzle. [2017-12-01]. （原始內容存檔於2020-11-15）.
- ^ "mutual recursion （頁面存檔備份，存於網際網路檔案館）", PlanetMath
- ^ On the Conversion of Indirect to Direct Recursion by Owen Kaser, C. R. Ramakrishnan, and Shaunak Pawagi at State University of New York, Stony Brook (1993)
- ^ Reynolds, John. Definitional Interpreters for Higher-Order Programming Languages (PDF). Proceedings of the ACM Annual Conference. Boston, Massachusetts: 717–740. August 1972 [2017-12-01]. （原始內容存檔 (PDF)於2011-06-29）.
- Harper, Robert, Programming in Standard ML, 2000 [2017-12-01], （原始內容存檔於2020-06-29）
- Harvey, Brian; Wright, Matthew. Simply Scheme: Introducing Computer Science. MIT Press. 1999. ISBN 978-0-26208281-5.
- Hutton, Graham. Programming in Haskell. Cambridge University Press. 2007. ISBN 978-0-52169269-4.
外部連結
[編輯]- Mutual recursion（頁面存檔備份，存於網際網路檔案館） at Rosetta Code
- "Example demonstrating good use of mutual recursion（頁面存檔備份，存於網際網路檔案館）", "Are there any example of Mutual recursion?（頁面存檔備份，存於網際網路檔案館）", Stack Overflow