再帰の打ち切りのバックアップ(No.1)

再帰の打ち切り

数値を用いた構文において必ず利用されるのは, 0以下の数値関数は消滅するという性質です.
これを再帰関数に応用すると, 再帰関数を打ち切ることができます.

a(X,T):XXXXa(sX,T-1)
a(r,10)

再帰関数

a(X):XXXXa(sX)
a(r)

が10回で打ち切られていることが分かると思います.

再帰的に構成できるパーツ複数の場所で使いたいときに便利な考え方ですね.
さらに引数を様々に変化させることで, 同じような再帰で書けるものを同時に定義できます.
つまり, 例えば上述の関数でも,

a(,6)

とすれば, 正面にたくさん進むパーツが得られますし,

a(rr,10)

とすれば, 長さ9の棒を正面に立てることができます.
場合によっては, 再帰関数を多変数化して幅を持たせる余分な引数を持たせる

a(X,Y,T):XXXXa(sYX,Y,T-1)

なんていうのも有効なときもあります.

a(r,,10)a(l,rsl,5)

などと育てる初項や育てる規則をある程度自在にコントロールできますね.

このように色んなパーツを兼ねた良い関数を定義するのは重要な問題意識だと思います. ただし汎用性を持たせるために関数を膨らませすぎると, かえってバイト数がかさむので, さじ加減が難しいですね.

次に再帰関数の右側を利用することを考えます. 通常の再帰関数では,
バグを楽しむ以外の目的では, 基本的に実行されない部分ですね.

a(X,T):XXXXa(sX,T-1)srsl
a(r,10)

この例を調べると分かると思いますが, 数値関数の右側は,
数値が0になり再帰が行われなくなった途端に溜まっていた分が吐き出される仕組みです.
ここに方向転換や移動を混ぜることにより, より効率的にパーツを作れることがあります.

「数値が0になった途端に右側が実行される」仕組みを利用して,
「再帰を打ち切って繰り返す」ことが可能になります.

a(X,T):lXlXsa(sX,T-1)a(l,9)
a(l,9)

a(l,9)が実行されて打ち切られた後再びa(l,9)が呼び出されることが分かるでしょう.
すると, 再びa(l,9)が実行されたあとでa(l,9)が呼び出されますね. したがってa(l,9)の無限ループに突入します.

a(X,T):lXlXsa(sX,T-1)sssra(l,9)
a(l,9)

などと, パーツ間に移動を挟むこともできます.

a(X,T):lXlXsa(sX,T-1)a(l,9)
a(l,5)

というように, 繰り返しの初項を特殊なものにすることもできますね.
12B構文?との複合も可能そうです.

a(X,T):lXlXsa(sX,T-3)a(l,T+10)
a(l,1)

また, 無限に繰り返したいだけが目的の場合は,

a(X,T):lXlXa(sX,T-1)a(l,9)
a(,1)

のように初項は何でも良かったりします.