小を大で挟む

再帰の打ち切りにおいて, さらに数値関数の右側を利用した

a(X,T):[1]a([2],T-1)[3]

の構文を考えてみましょう. [1],[2],[3]には適当なXの式が入ると考えてください.
Xは[2]の規則に従って成長していくのでそれをX0,X1,…と書くことにしましょう.
たとえばa(**,3)というような実行をするとします.このとき次の順番で実行されることがわかります.

X0に対する[1]

X1に対する[1]

X2に対する[1]

X2に対する[3]

X1に対する[3]

X0に対する[3]

つまり,最も成長した項が実行の中央段階になることがわかりますね.
「小で大をはさむ」というような理解をしておくと頭に入れやすいと思います.具体例としては,たとえば

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

などのコードがあるでしょうか.なお,[1]や[3]の部分に何も書かないコードも
ありますが,これもある意味では「小で大をはさむ」の1種と考えることができます.
同様の動きを数値のない再帰で育てようとすると3変数かかったりして実は結構大変です.
「a(X,Y,Z):a(sX,YX,XZ) と育ててYZと実行する」ような羽目になるのだと思います.
なお一見似ているコードとしては

a(X,Y):Ya(sX,XYX)
a(r,)

のようにして,Yの前後に付け足していくことが考えられますが,
これは見た目の類似とは裏腹に,「大で小を挟む」が実現されます.


つまり,数値と再帰の特性は

という標語で捉えておくと良いと思っています.
「同程度に素直に書ける」ならば再帰の方がバイト数が短く済むことが多いですが,
小で大を挟むようなコードを無理やり再帰で書くのは損になることが多いです.


もっとも,これは経路認識(パターンの区切り)を固定して考えた場合の話で,同じ問題が
「小で大を挟む経路だ!」「大で小を挟む経路だ!」という複数の解釈を持つことは よくある話なので,
経路認識を固定しないで問題に当たることが最も重要だったりするかも.
例えばHOJ voterでもコメントしたのですが,0439[X]では数値でも再帰でもClear可能です.
それぞれパターンの区切りをどう解釈するべきか考えてみてください
(この辺の選択が正しいのにClearに届かない人は棒の作り方がまずいかも).
この「数値の基本構文」の利用方法としては,それ1発で解けるというときもあれば
「小で大を挟む」型のボムとして利用する(特に連打する)ことも多いです.例えば,

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

とかでしょうか.繰り返しに放り込んだだけですね.
「育てたパターンを連打したい」ときには,再帰で育てる場合は,
育てたパターンを育ちすぎる前に適切な回数連打する必要がありますが,
数値で育てた場合は育つ途中が実行されず,育ちすぎていく心配もないので,
たくさん繰り返すなどの融通は利きやすいです.

再帰でやると位置合わせや向き合わせの苦労が多い場合にお勧めでしょうか.
特に,壁の影響で「十分たくさん繰り返せばそのうち経路に乗る」というようなときは,
数値で書いた方が確実に落ち着いて位置合わせできる気がします.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-02-12 (火) 22:42:13 (4083d)