[[HOJ講座]]
*多重再帰構文！ [#m8f29a28]
''多重再帰構文''とは、
 a(X):αXa(a())
 a()
上のコードの''a(a())''のように、再帰関数を２重(あるいはそれ以上)にして呼び出す構文のことです。

一見意味がなさそうに見えますが、この構文にはある効果があります。

とりあえず、下のコードを実際に展開してみましょう。(ギリシャ文字は、例えば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()で置換できる」''という効果があるのです。
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS