再帰を用いたプログラムと再帰を用いないプログラム
では、プログラムの読みやすさや計算にかかる手間は
どうちがうんでしょうか?

A 回答 (3件)

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++)
    • good
    • 0
この回答へのお礼

どうもありがとうございました

お礼日時:2001/06/14 23:26

一長一短があると言うことを説明したいので例えを使います。


鶴亀算を解くのに小学生なら鶴亀算の方がよくわかります。
しかし、高校生なら、2元1次方程式の方が理解しやすいでしょう。

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

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

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

どうもありがとうございました

お礼日時:2001/06/14 23:28

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



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

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

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

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

どうもありがとうございました

お礼日時:2001/06/14 23:30

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ