相互再帰は，複数の関数の間で呼び出し合うことで再帰となっているものです．関数それぞれは自分自身を呼び出す自己再帰ではなく，気づかず無限ループとなってしまったということもある形式です．言語記述解析では，文章構造（構文）が相互再帰となっていることもあって，むしろ積極的に使われることが多い形式でもあります．
この相互再帰を，様々なプログラミング言語のラムダ式（無名関数，無名メソッド）のみでやってみようというのがこの記事の趣旨です．
相互再帰の例（偶数奇数判定）
Pythonでの記述例は次の通り．余りを求める演算なしに定義できる例でもあるのですが，1を引くたびに関数呼び出しをしているため，値が大きくなるとほとんどの言語処理系で再帰制限エラーとなります．
Python(3.7.3)
>>> def even(x): return True if x == 0 else odd(x - 1)
...
>>> def odd(x): return False if x == 0 else even(x - 1)
...
>>> even(100)
True
>>> odd(100)
False
>>> even(101)
False
>>> odd(101)
True
>>> even(998)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 1, in even
File "<stdin>", line 1, in odd
File "<stdin>", line 1, in even
File "<stdin>", line 1, in odd
...
File "<stdin>", line 1, in odd
File "<stdin>", line 1, in even
RecursionError: maximum recursion depth exceeded in comparison
>>>
ラムダ式による相互再帰
ラムダ式による自己再帰は不動点コンビネータを用いることになりますが，今回は自己ではないので，他者（？）を呼び出す仕組みが必要となります．呼び出すための名前を大域環境で付けることができないのであれば，大域環境に相当するラムダ式を用意して名前束縛すれば良いことになります．ただし，ラムダ式は通常レキシカルスコープであるため，上位ラムダ式の引数として束縛した名前のラムダ式同士がお互いの名前を使用することは，そのままではできません（原初LISP評価器や当初のEmacs Lispはダイナミックスコープのため可能です）．ここでは，上位ラムダ式で束縛した名前をお互いの引数とすることで解決することを考えます．
上記の考え方に沿って相互再帰の例をPythonで書き直した記述例は次の通り．
Python(3.7.3)
>>> (lambda even,odd: even(100,even,odd))(
... lambda x,even,odd: True if x == 0 else odd(x-1,even,odd),
... lambda x,even,odd: False if x == 0 else even(x-1,even,odd))
True
>>> (lambda even,odd: odd(100,even,odd))(
... lambda x,even,odd: True if x == 0 else odd(x-1,even,odd),
... lambda x,even,odd: False if x == 0 else even(x-1,even,odd))
False
>>> (lambda even,odd: even(101,even,odd))(
... lambda x,even,odd: True if x == 0 else odd(x-1,even,odd),
... lambda x,even,odd: False if x == 0 else even(x-1,even,odd))
False
>>> (lambda even,odd: odd(101,even,odd))(
... lambda x,even,odd: True if x == 0 else odd(x-1,even,odd),
... lambda x,even,odd: False if x == 0 else even(x-1,even,odd))
True
>>>
各言語での記述例
Python以外の記述例を次に示しますが，いずれの記述もリファレンス実装のPython版と同じ構造であるため，ラムダ式や三項演算子などの記述方法の違いの一覧程度の意味しかないかもしれません（ヒドス）．
Scheme(Gauche0.9.10)
gosh> ((lambda (even odd) (even 100 even odd))
(lambda (x even odd) (if (= x 0) #t (odd (- x 1) even odd)))
(lambda (x even odd) (if (= x 0) #f (even (- x 1) even odd))))
#t
gosh> ((lambda (even odd) (odd 100 even odd))
(lambda (x even odd) (if (= x 0) #t (odd (- x 1) even odd)))
(lambda (x even odd) (if (= x 0) #f (even (- x 1) even odd))))
#f
gosh> ((lambda (even odd) (even 101 even odd))
(lambda (x even odd) (if (= x 0) #t (odd (- x 1) even odd)))
(lambda (x even odd) (if (= x 0) #f (even (- x 1) even odd))))
#f
gosh> ((lambda (even odd) (odd 101 even odd))
(lambda (x even odd) (if (= x 0) #t (odd (- x 1) even odd)))
(lambda (x even odd) (if (= x 0) #f (even (- x 1) even odd))))
#t
gosh>
Ruby(2.5.5/irb--simple-prompt)
>> ->even,odd{even[100,even,odd]}[
?> ->x,even,odd{x==0 ? true : odd[x-1,even,odd]},
?> ->x,even,odd{x==0 ? false : even[x-1,even,odd]}]
=> true
>> ->even,odd{odd[100,even,odd]}[
?> ->x,even,odd{x==0 ? true : odd[x-1,even,odd]},
?> ->x,even,odd{x==0 ? false : even[x-1,even,odd]}]
=> false
>> ->even,odd{even[101,even,odd]}[
?> ->x,even,odd{x==0 ? true : odd[x-1,even,odd]},
?> ->x,even,odd{x==0 ? false : even[x-1,even,odd]}]
=> false
>> ->even,odd{odd[101,even,odd]}[
?> ->x,even,odd{x==0 ? true : odd[x-1,even,odd]},
?> ->x,even,odd{x==0 ? false : even[x-1,even,odd]}]
=> true
>>
JavaScript(Node.js10.24.0)
> ((even,odd)=>even(100,even,odd))(
... (x,even,odd)=>x==0 ? true : odd(x-1,even,odd),
... (x,even,odd)=>x==0 ? false : even(x-1,even,odd))
true
> ((even,odd)=>odd(100,even,odd))(
... (x,even,odd)=>x==0 ? true : odd(x-1,even,odd),
... (x,even,odd)=>x==0 ? false : even(x-1,even,odd))
false
> ((even,odd)=>even(101,even,odd))(
... (x,even,odd)=>x==0 ? true : odd(x-1,even,odd),
... (x,even,odd)=>x==0 ? false : even(x-1,even,odd))
false
> ((even,odd)=>odd(101,even,odd))(
... (x,even,odd)=>x==0 ? true : odd(x-1,even,odd),
... (x,even,odd)=>x==0 ? false : even(x-1,even,odd))
true
>
備考
更新履歴
- 2021-07-16：初版公開