相互再帰

相互再帰（そうごさいき、テンプレート:Lang-en-short）は再帰の一種であり、直接的にそれ自身に対する再帰になっているのではなく、複数の関数などの間で相互に再帰になっているものである。

数学

以下の関数 A(x) と B(x) は相互再帰である。

$A(x)=\{\begin{array}{cc}1& ,x\le 1\\ B(x+2)& ,x>1\end{array}$

$B(x)=A(x-3)+4$

方程式によっては、相互再帰は、複雑系やカオス理論へとつながることもある。

プログラミング言語

テンプレート:ウィキプロジェクトリンク テンプレート:ウィキポータルリンク 相互再帰は関数型プログラミングでは非常に一般的で、LISP、Scheme、MLなどのプログラミング言語でのプログラムに多く使われている。Prologのような言語では、相互再帰の使用は避けられない。再帰下降パーサなど、手続き型プログラミングでも使われる手法である。

プログラミングスタイルによっては、相互再帰を禁止することもある。というのも、無限に再帰呼び出しし続けるコードを書かないようにすることも、そのようなコードを検出して修正することも難しいためである。 テンプレート:Software-stub