互遞歸

互遞歸是數學與計算機科學中一種遞歸，指兩個數學或計算機對象如函式或數據類型互相定義。互遞歸在函式程式語言或某些問題域中非常常見，如遞歸下降分析器，其中數據類型是自然地互相遞歸定義的。

基本介紹

• 中文名：互遞歸
• 學科：計算機

例子

數據類型

採取互遞歸定義的最重要的基本數據類型是樹。這可以用於定義森林（數的列表）:

f: [t[1], ..., t[k]]t: v f

森林f由一棵樹的列表組成，同時一棵樹t由一對：值v與森林f(子樹)構成。這種定義是精緻的，易於工作的抽象性（如用於證明關於樹的屬性的定理），因為它用簡單術語表示一棵樹：一個類型的列表，兩個類型組成的一對。而且它匹配許多關於樹的算法，這些對值做一些事，對子樹做另外一些事。

這種互遞歸定義可以轉換為單個遞歸，這是通過森林定義內部化：

t: v [t[1], ..., t[k]]

一顆樹t包含一對：值v與子樹的列表。這個定義更緊緻，但是更難以處理：一棵樹是一種類型的值與另一種類型的列表組成的一對，這要求解析開以證明結果。

在Standard ML，樹與森林可互遞歸定義如下，允許空樹：

datatype 'a tree = Empty | Node of 'a * 'a forestand 'a forest = Nil | Cons of 'a tree * 'a forest

計算機函式

如同在遞歸數據類型上的算法可以自然由遞歸函式給出，互遞歸數據結構上的算法可自然地由互遞歸函式給出。常見例子包括樹與遞歸下降解析器。如同直接遞歸，對遞歸深度很大或者是無窮的情形尾調用最佳化是必須的，如使用互遞歸的多任務。注意一般的尾調用最佳化比作為特例情況的尾遞歸調用最佳化更難實現，因此有效實現互尾遞歸未被很多語言考慮。對Pascal語言要求先聲明後使用，互遞歸要求前向聲明。

如同直接遞歸函式，包裝函式（wrapper function）對互遞歸函式是有用的作為包裝函式的作用域內的嵌套函式（如果支持的話）。這對跨多個函式共享狀態而不直接傳遞參數特別有用。

基本例子

一個例子用於確定奇偶數。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)棧空間，除非重寫用跳轉代替調用。

對於樹，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證明,構造單個函式F依次列出單個遞歸函式的值:{\displaystyle F=f_{1}(0),f_{2}(0),f_{1}(1),f_{2}(1),\dots ,}，重寫互遞歸為原始遞歸。

任何兩個過程之間的互遞歸可以轉換為直接遞歸，這通過把一個過程內聯至另一個過程實現。

任何數量的互遞歸過程可以合併為單一過程，這通過標籤聯合(一種代數數據類型)表示選擇過程與它的參數。這可以看作defunctionalization的有限套用。