再帰について

質問

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

回答No.1

ametsuchi · ベストアンサー

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

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

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

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

と３つ比較しましたが、速い順にａ）ｃ）ｂ）。しかもｂ）はスタックオーバーフロー連発でした。ｂ）とｃ）に差が出たのは、「関数呼び出しのオーバーヘッド」しか考えられません。関数を呼び出すと、レジスタの内容なんか全部スタックに保存しますから...。

お礼

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

回答No.3

ametsuchi

No.1の補足です。

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

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

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

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

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

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

５） STL（Stereo Lithography）データをOpen-GLでSmoothShadingする際、近傍頂点グループの分類にBalanced Octreeを使用。数10万Polygonのため、総当たりだと日が暮れる。（C++）

お礼

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

回答No.2

ymmasayan

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

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

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

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

お礼

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