(View this PageEdit this PageUploads to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide)
[blog] [ML] [todo] [CVS] [bug] [apache log] [swiki log] [statistics] [map] [man] [info] [アンテナ]

再帰

Recursion

関数自身が、自分（関数）を呼ぶこと。っていうと、あまりにも大雑把
であるが、まあそういうことなのである。
昔、学校で習うような、階乗なんて、もろ再帰である。
F(x) = x × F(x-1) (ただし、xは、自然数)

で、再帰っていうのは、自然な考え方なんですが、賢くないコンパイラ
だと、そのままのアセンブラを吐き出しちゃう。

これの何が問題かっていうと、C言語の場合だと、関数をコールするたび
に、フレームポインタっていうか、スタックにレジスタ退避するでしょ。
仮に、１回の関数コールで、100byte退避する（実際は、そんなに退避
しないけど）とすると、10000回再帰で呼び出すと100×10000 = 約1MB
も退避用のメモリを必要とする。

最近のコンピュータでは、これしきはどうってことないかと思うけど、
実は、このようにデータに依存して、メモリ量が著しく増大する
ことそのものが危険なのである。

つまり、データによって、システムに脆弱性が生じるということが
危険なのである。

ただし、最近の賢いコンパイラは、ちゃんと再帰を反復に置き換える
（置き換えられる再帰である末端再帰なら。)ことができるはず
なので、よく考えて使うべし。

-----------

ツッコミ大歓迎





-----------

Links to this Page