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

このQ&Aに関連する最新のQ&A

A 回答 (3件)

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



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

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

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

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

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

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

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

このQ&Aに関連する人気のQ&A

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

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

このQ&Aと関連する良く見られている質問

Q再帰処理を非再帰処理に書き換える場合

TreeViewなど階層数・要素数が動的に変化し
それらすべての要素に対して一括処理をするといった
本質的に、真に再帰的な操作をしなければならないような場合なのですが

状況説明のため少ないメンバに絞ると
こんなノードの抽象クラスがあるとします

namespace TreeView { namespace Node { class Super; }}
class MemoryMap;

class TreeView::Node::Super {

protected:

typedef Super* PTR;
PTR next, child;

Super();
virtual ~Super();
virtual Void Save( MemoryMap* ) const = 0;

public:

static Void Release( PTR* pp );
template <class T> static Void Release( T** pp ){ Release( (PTR*)pp ); }

};


んで

using TreeView::Node::Super;

Super::Super() : next(NULL), child(NULL){}
Super::~Super(){}

こんな感じにしといて、任意に追加、挿入しときますと

その後一括解放のためのReleaseの本体は

Void Super::Release( PTR* pp ){

for ( PTR p; p = *pp; ){
if ( p->child ) Release( &p->child );
*pp = p->next;
delete p;
}

}

こんな感じで、再帰を使えば結構簡単に書けると思うのですが


・・・利用法から考えてよっぽどないとは思うのですが
やはりそこは一応
スタックオーバーフローの危険性をコードサイドから積極的に
ほぼ回避しておくべきと考えると

階層数の上限を設けておいて
最低、追加・挿入時には、それをチェックする

というのが良いかと思うのですが

仮に別のアプローチで
こういった類の再帰(もっと複雑な場合のが多いかも)を非再帰関数に直すには
やっぱり


・goto文
・自分でヒープ上などに作る疑似スタック
・そのスタックに、gotoのジャンプ位置を保存できるenumとかの定数フラグ


などを使用せざるを得ない
って感じになってくるんでしょうかね?

TreeViewなど階層数・要素数が動的に変化し
それらすべての要素に対して一括処理をするといった
本質的に、真に再帰的な操作をしなければならないような場合なのですが

状況説明のため少ないメンバに絞ると
こんなノードの抽象クラスがあるとします

namespace TreeView { namespace Node { class Super; }}
class MemoryMap;

class TreeView::Node::Super {

protected:

typedef Super* PTR;
PTR next, child;

Super();
virtual ~Super();
virtual Void Save( MemoryMap* ) const = 0;

public:

static Voi...続きを読む

Aベストアンサー

別にgotoは使わなくてもいいんじゃないですか?
PTRをスタックするだけで。
ループの繰り返し

void Super::Release( PTR* pp ){
std::stack<PTR> sp; // スタックの準備
sp.push(*pp) ; // 次に処理したいノードをスタックに積む
// 関数での引数に相当。

while ( ! sp.empty() ){ // スタックが空→終了
// トップの内容を見る。スタックは変化しない
// 関数で引数の受け取りに相当
PTR p = sp.top() ;

if( p == NULL ) {
// 関数でのreturnに相当
sp.pop() ; // topは処理済みになるのでスタックから削除
continue ; // 次へ
}

if ( p->child ) { // 子があったら、
sp.push(p->child) ;// 子をスタックへ積んで
continue ; // 次へ:再帰呼び出しに相当
}

sp.push(p->next); // 次の候補であるp->nextをスタックに積む

*pp = p->next;
delete p;

sp.pop() ; // topは処理済みになるのでスタックから削除

}
}

別にgotoは使わなくてもいいんじゃないですか?
PTRをスタックするだけで。
ループの繰り返し

void Super::Release( PTR* pp ){
std::stack<PTR> sp; // スタックの準備
sp.push(*pp) ; // 次に処理したいノードをスタックに積む
// 関数での引数に相当。

while ( ! sp.empty() ){ // スタックが空→終了
// トップの内容を見る。スタックは変化しない
// 関数で引数の受け取りに相当
PTR p = sp.top() ;

if( p == NULL ) {
// 関数でのreturnに相当
sp.pop() ; // topは処理済みになるのでスタックから削除
co...続きを読む

Q再帰関数を用いて配列の合計を求める

かなり(約三時間)悩んでまだ分からないので質問します。
再帰関数を用いて配列の中の数字(floatで定義されている)の合計を求めるプログラムを作っています。階乗を求めるプログラムの例を見ながらやっているのですがもう降参です。簡単だと思ったんですけど配列と組み合わせでもう頭がパニックです。どなたか答え(またはヒント)を教えてください。

よろしくお願いします。
なお、下のプログラムは私が1から作りましたので完全に間違っている可能性大です。参考にしないでください。(^^ゞ

#include <iostream>
using namespace std;

float recur(int numF);

int main()
{
int num;
float sum;

cout << "Enter an integer number: ";
cin >> num;

//再帰関数なんてこうやれば使わなくても出来るのに~!
//for(i=0; i<num; i++)
//sum += array[i];

sum = recur(num);

cout << "The sum of all the numbers: " << sum << endl;

return 0;
}

float recur(int numF)
{
int i;
float array[numF]; //定数式が必要です、と怒られる

for(i=0; i<numF; i++)
return array[i] += array[i-1]; //ここに再帰の式が必要
}

かなり(約三時間)悩んでまだ分からないので質問します。
再帰関数を用いて配列の中の数字(floatで定義されている)の合計を求めるプログラムを作っています。階乗を求めるプログラムの例を見ながらやっているのですがもう降参です。簡単だと思ったんですけど配列と組み合わせでもう頭がパニックです。どなたか答え(またはヒント)を教えてください。

よろしくお願いします。
なお、下のプログラムは私が1から作りましたので完全に間違っている可能性大です。参考にしないでください。(^^ゞ

#include <iostre...続きを読む

Aベストアンサー

#2 です。二つ目、間違えた。

>   return sum(array, num - 1) + array[0];

  return sum(array, num - 1) + array[num - 1];

# 確認してません。って、この間違いを見ても分かるか (^^;

Q再帰関数とユークリッドの互除法を用いて最大公約数を求める

学校の課題で、再帰関数とユークリッドの互除法を用いて10~100000までの最大公約数を求めるという問題が出て自分でプログラムを作ってみたのですが無限ループに入ったり、関数が使えてないみたいでできません。プログラムを見て頂いて、どこを改善したらいいかを教えてください。

#include <stdio.h>

/* 正整数 n, m の最大公約数を計算する */
int gcd(int n, int m) {
int res;

res = n % m;

if (res == 0)
return m;/* 最大公約数が求まった */

return gcd(m, res);/* 再帰呼び出し */
}

int main(void) {
int i,j;

for(i=10000;i>=10;i--){
for(j=10;j=10000;j++){
printf("%d to %d no saidaikouyakusuu ha %d \n", i, j, gcd(i, j));
}
}

return (0);
}

です。期限が今日の夜までで、ぎりぎりなんですがよろしくお願いします。

学校の課題で、再帰関数とユークリッドの互除法を用いて10~100000までの最大公約数を求めるという問題が出て自分でプログラムを作ってみたのですが無限ループに入ったり、関数が使えてないみたいでできません。プログラムを見て頂いて、どこを改善したらいいかを教えてください。

#include <stdio.h>

/* 正整数 n, m の最大公約数を計算する */
int gcd(int n, int m) {
int res;

res = n % m;

if (res == 0)
return m;/* 最大公約数が求まった */

return gcd(m, res);/* ...続きを読む

Aベストアンサー

未検証
>for(j=10;j=10000;j++){
少なくとも真ん中の条件の=は誤り。それ以外に思いつくミスは特にない

Q再帰プログラム

strに格納されている文字数を数えるプログラムです。

#include<stdio.h>

int rstrlen(char *);

int main(void)
{
char str[] = {"abcdefghijk"};
printf("文字数:%d\n",rstrlen(str));
return 0;
}
int rstrlen(char *p)
{
if(*p) {
p++;
printf(p);
return 1 + rstrlen (p);
}
elsereturn 0;
}

return 1 + rstrlen (p);の部分で再帰をし1をプラスすることにより文字数をカウントしmainのprintfで文字数を表示しているのですがカウントしている値はどこに格納していてどのようにmainに返しているのかが分かりませんでした。教えてください。

Aベストアンサー

rstrlen("abc")
→ (1 + rstrlen("bc"))
→ (1 + (1 + rstrlen("c")))
→ (1 + (1 + (1 + rstrlen("")))
→ (1 + (1 + (1 + (0))))
→ (1 + (1 + (1 + 0)))
→ (1 + (1 + (1)))
→ (1 + (1 + 1))
→ (1 + (2))
→ (1 + 2)
→ (3)
→ 3

()が付くのがコール,外れるのがリターンです。
カウントしている値は関数の中に格納されていると言えなくもない。

Q再帰プログラム

#include<stdio.h>

int rstrlen(char*);

int main(void)
{
char str[100];

printf("文字列を入力してください\n");
gets(str);

printf("文字数は %d です\n",rstrlen(str));

return 0;
}
int rstrlen(char *p)
{
if(*p){
p++;
return 1+rstrlen(p);
}

else
return 0;
}
文字数を計算するプログラムです。
if(*p)の*pとはNULLを表しているのですか?

Aベストアンサー

 「rstrlen」を見てみます。ここには,char へのポインタ p が入って呼び出されます。

 ここでの,if (*p) は,if (*p != '\0') と同じです。ですから,「p の指す先の文字がヌル文字(=終端)でなかったら」です。このとき,p の指す先を 1 だけ増やして,再帰し,その戻り値に 1 を加えます。一方,ヌル文字だったらそこで再帰は停止し,0 を返します。


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

おすすめ情報