【Ｃ言語】再帰が時間がかかる理由について

再帰のプログラムがなぜ時間がかかるのかを詳しく調べています。

アセンブリレベルで見ると、
callに時間がかかるのか？それともpop命令？それとも退避？
結局、よく分からないまま、
Ｇｏｏｇｌｅ検索して調べています。（まだよくわかってません。）

再帰呼び出しのデメリットは、
スタック領域を大量に消費する、関数呼び出しのオーバーヘッドであること。

この事実はわかりました。
しかしながら、
オーバーヘッドとは具体的に何なのか
これを調べています。

どなたか、良いサイト・書籍を知らないでしょうか。
教えてください。

No.3 ベストアンサー 回答者： jjon-com 回答日時： 2013/02/27 00:19

２つの要因があると思います。

--------
１つ目は次の例のように，再帰的定義の中に自分自身が１つだけ登場する場合です。

「１からｎの総和」
F(n)＝n＋F(n-1) …（n＞1 であること）
F(1)＝1

F(5)
＝5＋F(4)
＝5＋(4＋F(3))
＝5＋4＋(3＋F(2))
＝5＋4＋3＋(2＋F(1))
＝5＋4＋3＋2＋1

この場合，上記に示したように，結果的に行われる計算自体は次のループと変わらず，5＋4＋3＋2＋1 を行っています。

s = 0;
for (i = n; i >= 1; i--) {
s = s + i;
}

しかし，5,4,3,2,1のそれぞれを求めるために再帰では毎回関数呼び出しを用いています。
回答No.1・No.2の指摘どおり「関数呼び出しを用いること自体がオーバヘッドである」ということです。

--------
２つ目は次の例のように，再帰的定義の中に自分自身が複数登場する場合です。

「フィボナッチ数」
F(n)＝F(n-1)＋F(n-2) …（n≧2 であること）
F(1)＝1
F(0)＝0

F(5)
＝F(4)＋F(3)
＝(F(3)＋F(2))＋(F(2)＋F(1))
＝{(F(2)＋F(1))＋(F(1)＋F(0))}＋{(F(1)＋F(0))＋1}
＝[{(F(1)＋F(0))＋1}＋(1＋0)]＋{(1＋0)＋1}
＝[{(1＋0)＋1}＋(1＋0)]＋{(1＋0)＋1}
＝5

フィボナッチ数は，0, 1, 1, 2, 3, 5, 8, 13, 21, 44, ……のように列挙できる，前２者の和です。

この再帰の場合，前述の「関数呼び出し自体がオーバヘッドである」ことはもちろんなのですが，加えて「関数呼び出しの回数が増えていること」が新たなオーバヘッドとなります。

具体的には，次の★で示したF(2)を求める箇所（ちなみに，F(2)＝F(1)＋F(0)＝1＋0＝1です）は３つ登場しますが，

F(5)
＝F(4)＋F(3)
＝(F(3)＋F(2)★)＋(F(2)★＋F(1))
＝{(F(2)★＋F(1))＋(F(1)＋F(0))}＋{(F(1)＋F(0))＋1}

ある★箇所で求めたF(2)の値を，他の★箇所で流用することは再帰では行われません。式が２つの項に分かれ，４つの項に分かれ，と分割されていきますが，ある一つの項で値を求める際，すでに他の項でその値が算出済であるかどうか知りませんし，自分が求めた値をそれを必要とするであろう他の項に教えようともしません。

再帰的定義の中に自分自身が複数登場する場合は，関数呼び出しの回数がネズミ算的に増えていきます。

No.2 回答者： chie65535 回答日時： 2013/02/26 15:53

再帰コールってのは、要は「現状の自分を保護したまま、自分自身を呼んで、帰って来た時に、呼ぶ前の状態にちゃんと戻っている」って必要がある。

この「自身の保護と、呼び出し前の状態への回復」が、オーバーヘッドになる訳。

再帰コールでは、特定の目的を除いては、グローバル変数は使えない。

「自分から帰って来た時」に、もし、グローバル変数の値が変わっていたら、「呼ぶ前と呼んだあとで、値が違う」って事になって「呼び出し前の状態への回復」が出来なくなる。

もし、ローカル変数を１００個使っているなら、ローカル変数１００個分の保護と復帰が必要。

そのローカル変数が、スタック上に置かれるオート変数なら、保護と復帰はスタックを操作するだけで済むけど、もし、スタック上に置けないなら「スタックや別のメモリ空間への退避と復帰」が必要になってしまう。

場合によっちゃ、１回再帰コールするだけで、数千バイトのメモリを転送する必要が出る場合もある。

もし再帰コールで「退避と復帰」が要らないなら、変数などはすべて「固定アドレスのメモリ」に置いておく事ができる。

例えば「最初に見付かったディレクトリがあったら、そのディレクトリでも同じ事をして、ディレクトリを連結した文字列を作る」って場合。

この場合は、自分を再帰コールしたとしてもお「自分から帰って来たら、あとは何もしない」ので、退避も復帰も不要な書き方が出来る。

退避と復帰が不要なら、再帰コールしても、スタックの消費は「戻りアドレス」だけで済むし、退避も復帰もしないから、通常の関数コールよりもオーバーヘッドは小さくなる。普通の関数コールだって、必要最低限の退避と復帰が必要になるからね。

そういう訳で、オーバーヘッドの大半は「退避と復帰」にあります。

No.1 回答者： zwi 回答日時： 2013/02/26 09:58

まぁ、Wikipediaなどは先に読みましょう。

「オーバーヘッド - Wikipedia」
http://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%BC% …

で、callなのか、pushなのか、popなのかですが、それらを含めた全てです。ループで表現した時には出てこない再帰だけにあるもの全てがオーバーヘッドとなります。
それとＣＰＵに依りますがcallで発生する命令キャッシュのフラッシュもオーバーヘッドになります。