-PR-
解決済み

再帰について

  • すぐに回答を!
  • 質問No.89891
  • 閲覧数505
  • ありがとう数6
  • 気になる数0
  • 回答数3
  • コメント数0

お礼率 16% (11/68)

再帰を用いたプログラムと再帰を用いないプログラム
では、プログラムの読みやすさや計算にかかる手間は
どうちがうんでしょうか?
通報する
  • 回答数3
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.1
レベル11

ベストアンサー率 31% (81/257)

1)プログラムの簡潔さ:再帰の方が遥かに簡潔でステップ数も少ない。

2)読みやすさ:モノによるでしょう。再帰と同じことはスタックを自分で管理すれば出来ます。これも結構分かり難い。

画像処理で「ラベリング」なんか考えると、再帰の方が遥かに楽で、「ラベリング」の定石通りに組むと結構大変で分かり難い。

3)計算時間:再帰は関数呼び出しのオーバーヘッドがかかります。以前、上の「ラベリング」処理で、
a)定石通り
b)再帰
c)再帰と同じ仕掛けを自分でスタック管理で実現

と3つ比較しましたが、速い順にa)c)b)。しかもb)はスタックオーバーフロー連発でした。b)とc)に差が出たのは、「関数呼び出しのオーバーヘッド」しか考えられません。関数を呼び出すと、レジスタの内容なんか全部スタックに保存しますから...。
お礼コメント
janne

お礼率 16% (11/68)

どうもありがとうございました
投稿日時 - 2001-06-14 23:30:40
-PR-
-PR-

その他の回答 (全2件)

  • 回答No.2
レベル14

ベストアンサー率 30% (2593/8599)

一長一短があると言うことを説明したいので例えを使います。
鶴亀算を解くのに小学生なら鶴亀算の方がよくわかります。
しかし、高校生なら、2元1次方程式の方が理解しやすいでしょう。

再帰も初心者にとっては、はなはだ難しいですし、トリッキーですが、論理的に整然としていますので、ベテランにとっては、プログラムが短くて、わかりやすいでしょう。

計算にかかる手間は、おそらく再帰の方がかかっているのでしょうね。

ただ、注意しないといけないのは、再帰で解かなくても解ける問題を、無理矢理、再帰で解いて見せている例が多いことです。検証がし易いからと言う理由は判るのですが、本当に再帰でないと解くのが難しい問題(ハノイの塔など)をもっとPRすべきなのでしょうね。バイナリーソートなども、再帰を使うととても短いステップで書けますね。
お礼コメント
janne

お礼率 16% (11/68)

どうもありがとうございました
投稿日時 - 2001-06-14 23:28:22


  • 回答No.3
レベル11

ベストアンサー率 31% (81/257)

No.1の補足です。

ymmasayanさんの言われる、「ハノイの塔」は遊びに属しますし、「バイナリ・ソート」も「qsort」という便利で強力なものがある以上、自力でプログラム書いても勉強にしかなりません。学生さんならこれでいいでしょうが、社会人の場合は「実務に生かしてナンボ」の世界です。ymmasayanさんはあくまで例として出しただけなんでしょうが...。

私自身が実務で使った例を述べます。昔は再帰のできないFortanが主でしたから、Fortranで再帰でなければ書けない場合に限り、スタックを自分で管理して再帰プログラムを書きました。Cが普及してからは、そんな面倒なことしません。

1) 3D地形上にまばらに分布する数1000件の建物を管理する際、「balanced Quad Tree」を使用。このように深さの決らない階層的データ構造は事実上再帰でしか書けない。(Fortran)

2) CADで作られた車の自由曲面データをCAM用に多面体近似する際、トリム曲面を
「Binary Tree」で管理し、指定トレランス以内まで分割。これも再帰でないと無理。(Fortran)

3) 電波伝播解析用に2D,3D-RayTraceをした際、電波が反射・回折・透過などで分岐することを再帰で表現(C)

4) 地下の地層に石油がどのように溜まるかシミュレートする際の連続領域検出用に(C)

5) STL(Stereo Lithography)データをOpen-GLでSmoothShadingする際、近傍頂点グループの分類にBalanced Octreeを使用。数10万Polygonのため、総当たりだと日が暮れる。(C++)
お礼コメント
janne

お礼率 16% (11/68)

どうもありがとうございました
投稿日時 - 2001-06-14 23:26:20
このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


専門家があなたの悩みに回答!

-PR-

ピックアップ

-PR-
ページ先頭へ