育たない再帰

例えば1変数の再帰の利用方法を考えてみましょう.

a(X):[1]a([2])
a([3])

ほとんどの再帰の用法は, [2]の部分でXを育てて, その育っていくXを
次々と同じ形の関数[1]に代入していくことにあるでしょう.
しかし実際には, Xを育てない利用方法もあります.


[2]の部分に1つでもXが含まれると, Xが大きくなっていきます.
したがって, Xを育てない構文は, [2]の部分にXが含まれないものです.
例えば次のコードを見てみましょう:

a(X):XXXra(ssr)
a(srsl)
non_grow_1.png

Xの部分にssrを代入し続けるので, ssrssrssrrを繰り返す形になりますが,
Xがrになり続けるのは第2項以降なので, 結果として,

srslsrslsrs, ssrssrssrr, ssrssrssrr, ssrssrssrr, ...

という繰り返しが実現されます.


このように, 再帰と言っても育つものばかりではありません.
なお, 原理的にはこれは特殊な初項で説明したのと全く同じ原理で,
0変数の再帰に特殊な初項を作るための変数Xを加えた格好になっています.
したがって, 特殊な初項に慣れている人にとっては当たり前の構文なんですが,
「育たない再帰」という発想自体が盲点になりやすい (実際, このテーマの出題は初期にはほとんど見当たりません)
と思います. 使ったことがない人はぜひ使える場面を探してみてください!


添付ファイル: filenon_grow_1.png 90件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-01-18 (金) 23:37:46 (2098d)