再帰について　

２　再帰関数について　　谷岡　慶

　　再帰関数の説明です。　　再帰のアルゴリズムとは，処理手順が自分自身を用いて定義されているもののことです。　　説明より例がわかりやすいでしょう。　　いつもの例として，階乗n!の計算を。　　階乗とは，　　n! = n × (n-1) × (n-2) × ... × 2 × 1 　　でしたね。　　これは再帰によって，こうも定義できます。　　n! = n × (n-1)! (n = 0 でないならば) 　　= 1 (n = 0 ならば) 　　!の定義のなかに，!が入ってます。これが再帰関数です。　　例えばつまり，4!なら　　4! = 4 × 3! 　　= 4 ×(3 × 2!) 　　= 4 ×(3 ×(2 × 1!)) 　　= 4 ×(3 ×(2 ×(1 × 0!))) 　　= 4 ×(3 ×(2 ×(1 × 1))) 　　 = 4 ×(3 ×(2 × 1)) 　　 = 4 ×(3 × 2) 　　 = 4 × 6 　　 = 24 　　こんな具合になります。　　こうしてみると，再帰関数は，一般形として　　　　再帰関数ｆ（代入値）において，　　　　　もし，代入値＝ある値であれば，ある処理をして終了　　　　　さもなくば，再帰関数ｆ（代入値－α）　　とわかりますね。　　つまり，ある終了条件に到達するまでは，なにがなんだかわからんままに命令を受けつづ　　けて，これだ！という終了条件に合致するある値に到達したとたん全てが納得される，と　　いうパタン。　　ドゥルーズらが文句をつけたい精神分析のパタンを，太田さんの発想どおり，見事にあら　　わしていると思います。　　なお，再帰関数は確かにものすごく強力で，相当なことをやってのけます。悟りさえ開き　　　　ます。　　聞いた話では，タイだかどっかのお寺では，64枚だか108枚だかのペグでハノイの塔を　　解くと悟りが開けるらしい。 http://www.ngm.ed.ynu.ac.jp/negami/dai3nori/sect2.html 　　の真ん中あたりにハノイの塔の説明が　　が，再帰を使えば，　　　再帰関数ハノイ（代入値＝ペグ枚数ｎ，棒ＸＹＺ）において，　　　　　もし，ｎ＝１であれば，　　　　　　　そのペグをＸからＹに動かして終了　　　　　さもなくば，　　　　　　　再帰関数ハノイ（ｎ－1，棒ＸＺＹ）において，　　　　　　　　　ｎ－１番目ののペグをＸからＺに動かして　　　　　　　さらに　　　　　　　ｎ番目のペグをＸからＺに動かして　　　　　　　さらに　　　　　　　再帰関数ハノイ（ｎ－1，棒ＺＹＸ）において，　　　　　　　　　ｎ－１番目ののペグをＹからＺに動かす　　で表現できちゃう。これまた，一番上のペグにルールが合致するまでその他の処理は保留　　　　されて，いったん動き出すと，ばばばばと動いていくパタンですね。　　でもコンピュータが悟りを開くのは何十億か何兆年か先の話になるんですが・・・。　　そんなハノイの塔ってなんじゃい？　悟りって何のこと？　　上にも書いた以下のwebサイトに，どの本より詳しい説明が。 http://www.ngm.ed.ynu.ac.jp/negami/dai3nori/index.html 　　ハノイ関数の説明の簡単わかりやすいバージョンは，アルゴリズム入門のページも近々開　　　　設する予定なので，譲ります。　　また，噂の分散表現に関するページをラカンのページに構築しつつあるので，時々見てみ　　　　てください。そのうち，ドゥルーズとかの話まで到達するはずです。

DGDトップページへ

塩田研究室・自主ゼミのページへ