再帰のプログラムがなぜ時間がかかるのかを詳しく調べています。
アセンブリレベルで見ると、
callに時間がかかるのか?それともpop命令?それとも退避?
結局、よく分からないまま、
Google検索して調べています。(まだよくわかってません。)
再帰呼び出しのデメリットは、
スタック領域を大量に消費する、関数呼び出しのオーバーヘッドであること。
この事実はわかりました。
しかしながら、
オーバーヘッドとは具体的に何なのか
これを調べています。
どなたか、良いサイト・書籍を知らないでしょうか。
教えてください。
No.3ベストアンサー
- 回答日時:
2つの要因があると思います。
--------
1つ目は次の例のように,再帰的定義の中に自分自身が1つだけ登場する場合です。
「1からnの総和」
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の指摘どおり「関数呼び出しを用いること自体がオーバヘッドである」ということです。
--------
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, ……のように列挙できる,前2者の和です。
この再帰の場合,前述の「関数呼び出し自体がオーバヘッドである」ことはもちろんなのですが,加えて「関数呼び出しの回数が増えていること」が新たなオーバヘッドとなります。
具体的には,次の★で示したF(2)を求める箇所(ちなみに,F(2)=F(1)+F(0)=1+0=1です)は3つ登場しますが,
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)の値を,他の★箇所で流用することは再帰では行われません。式が2つの項に分かれ,4つの項に分かれ,と分割されていきますが,ある一つの項で値を求める際,すでに他の項でその値が算出済であるかどうか知りませんし,自分が求めた値をそれを必要とするであろう他の項に教えようともしません。
再帰的定義の中に自分自身が複数登場する場合は,関数呼び出しの回数がネズミ算的に増えていきます。
No.2
- 回答日時:
再帰コールってのは、要は「現状の自分を保護したまま、自分自身を呼んで、帰って来た時に、呼ぶ前の状態にちゃんと戻っている」って必要がある。
この「自身の保護と、呼び出し前の状態への回復」が、オーバーヘッドになる訳。
再帰コールでは、特定の目的を除いては、グローバル変数は使えない。
「自分から帰って来た時」に、もし、グローバル変数の値が変わっていたら、「呼ぶ前と呼んだあとで、値が違う」って事になって「呼び出し前の状態への回復」が出来なくなる。
もし、ローカル変数を100個使っているなら、ローカル変数100個分の保護と復帰が必要。
そのローカル変数が、スタック上に置かれるオート変数なら、保護と復帰はスタックを操作するだけで済むけど、もし、スタック上に置けないなら「スタックや別のメモリ空間への退避と復帰」が必要になってしまう。
場合によっちゃ、1回再帰コールするだけで、数千バイトのメモリを転送する必要が出る場合もある。
もし再帰コールで「退避と復帰」が要らないなら、変数などはすべて「固定アドレスのメモリ」に置いておく事ができる。
例えば「最初に見付かったディレクトリがあったら、そのディレクトリでも同じ事をして、ディレクトリを連結した文字列を作る」って場合。
この場合は、自分を再帰コールしたとしてもお「自分から帰って来たら、あとは何もしない」ので、退避も復帰も不要な書き方が出来る。
退避と復帰が不要なら、再帰コールしても、スタックの消費は「戻りアドレス」だけで済むし、退避も復帰もしないから、通常の関数コールよりもオーバーヘッドは小さくなる。普通の関数コールだって、必要最低限の退避と復帰が必要になるからね。
そういう訳で、オーバーヘッドの大半は「退避と復帰」にあります。
No.1
- 回答日時:
まぁ、Wikipediaなどは先に読みましょう。
「オーバーヘッド - Wikipedia」
http://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%BC% …
で、callなのか、pushなのか、popなのかですが、それらを含めた全てです。ループで表現した時には出てこない再帰だけにあるもの全てがオーバーヘッドとなります。
それとCPUに依りますがcallで発生する命令キャッシュのフラッシュもオーバーヘッドになります。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
このQ&Aを見た人はこんなQ&Aも見ています
-
これ何て呼びますか Part2
あなたのお住いの地域で、これ、何て呼びますか?
-
フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
あなたが普段思っている「これまだ誰も言ってなかったけど共感されるだろうな」というあるあるを教えてください
-
映画のエンドロール観る派?観ない派?
映画が終わった後、すぐに席を立って帰る方もちらほら見かけます。皆さんはエンドロールの最後まで観ていきますか?
-
海外旅行から帰ってきたら、まず何を食べる?
帰国して1番食べたくなるもの、食べたくなるだろうなと思うもの、皆さんはありますか?
-
天使と悪魔選手権
悪魔がこんなささやきをしていたら、天使のあなたはなんと言って止めますか?
-
プログラムで関数は使わない方が速くなる?
その他(プログラミング・Web制作)
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
VBAの配列サイズとメモリに関して
-
C言語で、メモリを解放しないで...
-
CImage::ReleaseDC()のエラーで...
-
EXCEL-VBAにてADOのレコードセ...
-
メモリが不足しています(VBA)
-
ファミコンって8ビットしかない...
-
「ヒープサイズの設定」て何?
-
オブジェクトの開放
-
C言語初心者です。debug assert...
-
C言語:関数のメモリ上でのサイ...
-
C,C++プログラムの強制終了時の...
-
プログラムが偶然動く
-
C言語における再帰呼び出しの...
-
Apacheでバーチャルホストの最...
-
メモリ不足
-
「memcpy」と「strcpy」について
-
メモリアロケーション異常の発...
-
仮想メモリの増やし方
-
Tomcatによるバッチ処理時のメ...
-
メモリのセグメント違反の解決...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VBAの配列サイズとメモリに関して
-
C言語で、メモリを解放しないで...
-
大容量のメモリ確保をスワップ...
-
エクセル キャッシュメモリー...
-
エクセルのメモリ使用状況/Appl...
-
「ヒープサイズの設定」て何?
-
ExcelのVBAでメモリ解放できない
-
メモリの解放の仕方
-
メモリのセグメント違反の解決...
-
メモリ不足
-
ファイルマッピング関数で失敗
-
「memcpy」と「strcpy」について
-
closeとメモリの開放について
-
EXCEL-VBAにてADOのレコードセ...
-
マクロのスピードがダウンする??
-
VB.netでUSBメモリの固有I...
-
エクセルVBA 大容量CSVファイル...
-
メモリの消費量について
-
【C言語】再帰が時間がかかる...
-
プログラム実行中に強制終了
おすすめ情報