# 互递归

## 例子

### 数据类型

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

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

Standard ML，树与森林可互递归定义如下，允许空树：[2]

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

### 计算机函数

#### 基本例子

```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);
}
```

Python语言实现树的例子:

``` def f_tree(tree):
f_value(tree.value)
f_forest(tree.children)

def f_forest(forest):
for tree in forest:
f_tree(tree)
```

## 流行性

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.

## 参考文献

1. ^ 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.
2. ^
3. ^ Hutton 2007，6.5 Mutual recursion, pp. 53–55.
4. ^ "Mutual Tail-Recursion页面存档备份，存于互联网档案馆）" and "Tail-Recursive Functions页面存档备份，存于互联网档案馆）", A Tutorial on Programming Features in ATS页面存档备份，存于互联网档案馆）, Hongwei Xi, 2010
5. ^ Solving Every Sudoku Puzzle. [2017-12-01]. （原始内容存档于2020-11-15）.
6. ^ "mutual recursion页面存档备份，存于互联网档案馆）", PlanetMath
7. ^ 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)
8. ^ 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）.