相互再帰

相互再帰（そうごさいき、英: Mutual recursion）は再帰呼び出しの一種であり、2つの関数が互いを使って定義されているものをいう。

数学 [編集]

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

$A(x)=\begin{cases} 1 & , x\le1 \\ B(x+2) & ,x>1\end{cases}$

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

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

相互再帰は関数型プログラミングでは非常に一般的で、LISP、Scheme、MLなどのプログラミング言語でのプログラムに多く使われている。Prologのような言語では、相互再帰の使用は避けられない。

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

参照透過性の成立している言語では、相互再帰はあまり問題を生まないが、破壊的操作を行う関数同士で相互再帰を行うと、ロジックが複雑になりすぎて、カオス（混沌）となり、バグの温床となることが多い。