- ベストアンサー
再帰について
- みんなの回答 (3)
- 専門家の回答
質問者が選んだベストアンサー
1)プログラムの簡潔さ:再帰の方が遥かに簡潔でステップ数も少ない。 2)読みやすさ:モノによるでしょう。再帰と同じことはスタックを自分で管理すれば出来ます。これも結構分かり難い。 画像処理で「ラベリング」なんか考えると、再帰の方が遥かに楽で、「ラベリング」の定石通りに組むと結構大変で分かり難い。 3)計算時間:再帰は関数呼び出しのオーバーヘッドがかかります。以前、上の「ラベリング」処理で、 a)定石通り b)再帰 c)再帰と同じ仕掛けを自分でスタック管理で実現 と3つ比較しましたが、速い順にa)c)b)。しかもb)はスタックオーバーフロー連発でした。b)とc)に差が出たのは、「関数呼び出しのオーバーヘッド」しか考えられません。関数を呼び出すと、レジスタの内容なんか全部スタックに保存しますから...。
その他の回答 (2)
- ametsuchi
- ベストアンサー率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++)
お礼
どうもありがとうございました
- ymmasayan
- ベストアンサー率30% (2593/8599)
一長一短があると言うことを説明したいので例えを使います。 鶴亀算を解くのに小学生なら鶴亀算の方がよくわかります。 しかし、高校生なら、2元1次方程式の方が理解しやすいでしょう。 再帰も初心者にとっては、はなはだ難しいですし、トリッキーですが、論理的に整然としていますので、ベテランにとっては、プログラムが短くて、わかりやすいでしょう。 計算にかかる手間は、おそらく再帰の方がかかっているのでしょうね。 ただ、注意しないといけないのは、再帰で解かなくても解ける問題を、無理矢理、再帰で解いて見せている例が多いことです。検証がし易いからと言う理由は判るのですが、本当に再帰でないと解くのが難しい問題(ハノイの塔など)をもっとPRすべきなのでしょうね。バイナリーソートなども、再帰を使うととても短いステップで書けますね。
お礼
どうもありがとうございました
関連するQ&A
- javaの再帰呼びについてお願いします。
javaで nPn ,nCn 組み合わせ計算プログラムを 再帰呼びを使って 作成しようとしてますがとうやって書けばいいかわかりません。 初心者なんでわかりやすいコメントで お願いいたします
- 締切済み
- その他(学問・教育)
- 再帰呼び出しを使いますか?
趣味でプログラムをかじる程度なのですが、今まで自分はプログラムを作っていて再帰呼び出しを使ったことがありませんが、みなさんは良く使うのでしょうか? なかなか再帰呼び出しを考えるのが難しく自分のプログラムで適用すると良いところなど思い浮かびません。 再帰呼び出しをすると何か利点とかあるのでしょうか? 再帰呼び出しで無いと作るのが難しいプログラムなど今までありましたか?あればどんな処理だったかなど教えてください。
- ベストアンサー
- C・C++・C#
- プログラム構造の「再帰的」について
再帰的の説明に 「再帰的とは、あるプログラムがその内部から自分自身を呼び出して使用できる性質である。」「したがって再帰的であれば、必然的に再入可能でもある。」とありました。 ここで、「したがって再帰的であれば、必然的に再入可能でもある。」とは、つまり、プログラムAの中に再帰したプログラムA’が既に再入している状態にある、ということを表しているという理解かな?と思っているのですが、宜しいのでしょうか? より良い理解のために、補足説明などいただけたら、と思います。よろしくお願いいたします。
- ベストアンサー
- その他([技術者向] コンピューター)
- 再帰アルゴリズム
再帰アルゴリズムの練習のため問題に取り組んでいるのですが、問題集に解答がついておらずイマイチ理解できていないので教えていただけると助かります。 d個の毎インデックスで(0,0,...,0)から(n,n,...,n)まで反復させるアルゴリズムを反復アルゴリズムと再帰アルゴリズムの両方考えよ です。 (0,0,0,...,0) (1,0,0,...,0) (1,1,0,...,0) (1,1,.....,1) ... (n,n,.....,n) と表示を繰り返すプログラムでいいのかな、と思い反復の方は二十ループを用いてプログラムかけたんですが、再帰の法がアルゴリズムがどうも理解できていません。 ご教授願えればと思い、お願いします。
- 締切済み
- 科学
- javaの再帰関数のフローチャート
再帰プログラムを組むために、まずフローチャートを書こうと思ったのですが、再帰プログラムのフローチャートの書き方がわからなくなりました。 よかったら、わかりやすく回答よろしくお願いします!!
- 締切済み
- Java
お礼
どうもありがとうございました