多重再帰構文とは、
a(X):αXa(a()) a()
上のコードのa(a())のように、再帰関数を2重(あるいはそれ以上)にして呼び出す構文のことです。
一見意味がなさそうに見えますが、この構文にはある効果があります。
とりあえず、下のコードを実際に展開してみましょう。(ギリシャ文字は、例えばsrslなどを表していると考えてください)
a(X):αXa(a(β)) a()
a()を1つずつ展開していきます。
a() = αa(a(β)) = ααa(β)a(a(β)) = αααβa(a(β))a(a(β)) ..... = αααβααβ...ααβa(a(β)) [ここより右は永久に実行されない]
となります。
要するに
α+[ααβ]×無限
となっています。 さて、ここで単に
a(X):αXa(β) a()
とした場合と比べてみましょう。上のコードを展開すると、
a() = αa(β) = ααβa(β) ..... = ααβαβ...αβa(β) [ここより右は永久に実行されない]
となります。
要するに
α+[αβ]×無限
です。 二つを並べて比べてみると、
α+[ααβ]×無限 α+[αβ]×無限
違いは「繰り返し部分の先頭にαがくっついているかどうか」です。 つまり、この構文には「αをa()で置換できる」という効果があるのです。