- ベストアンサー
再帰呼び出しについて
C言語について質問があります。 平成13年春の基本情報処理技術者試験に出ていた問題なのですが， このプログラムの流れが分かりません。 void DrawCurve(int sx, int sy, int x1, int y1, int x2, int y2, int ex, int ey, int len){ int p1x, p1y, p2x, p2y, p3x, p3y; int p4x, p4y, p5x, p5y, p6x, p6y; /** 途中省略 **/ DrawCurve(sx, sy, p1x, p1y, p4x, p4y, p6x, p6y, len); /* ↑を(1)と名付けさせて頂きます */ DrawCurve(p6x, p6y, p5x, p5y, p3x, p3y, ex, ey, len); /* ↑を(2)と名付けさせて頂きます */ return ; } (1)の処理に入ったらDrawCurve関数の先頭に行くと思うのですが， そうすると(2)の処理とreturnは絶対行われない気がするのです。 それとも(1)の後(2)の処理に行くのでしょうか？ 再帰を間違って解釈してるのだと思います。 ご存知の方どうか教えてください。よろしくお願いします。
- __sourin__
- お礼率55% (10/18)
- C・C++・C#
- 回答数3
- ありがとう数4
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
>/** 途中省略 **/ のどこかに条件判定文か何かで return してないでしょうか？本当にこのままだとしたらスタックがオーバーフローするので一瞬のうちにプログラムがコケるはずです。 >(1)の処理に入ったらDrawCurve関数の先頭に行くと思うのですが， 分かっていらっしゃったとしたら、お節介かも知れませんが、これは先頭に戻るわけではありません。スタック上に新たな変数エリアや関数戻りアドレスなどが確保され関数が実行されます。だから同じ int p1x という名前の変数でも再入の回数分の複数の実体が存在することになります。 >それとも(1)の後(2)の処理に行くのでしょうか？ >再帰を間違って解釈してるのだと思います。 /** 途中省略 **/ 部分に return がない限り(2)には行かないと思います。
その他の回答 (2)
- SpiralGalaxy
- ベストアンサー率39% (649/1652)
>なるほど,関数は呼び出されるとスタックに確保されると聞いた事があります。 >ここで言われているのは入れ子の関数は全て違う関数として呼び出されるという事ですよね？ 「全て違う関数として呼び出される」というのは、正しいといってもよいのではないかと思います。 ただ関数そのものの実行コードは１ヶ所にしかありません。再入を繰り返すと関数自体がたくさんできるわけではなくて、その処理場所がたくさんできることになります（＝自動変数の保存場所、関数の戻りアドレス保存場所など）。関数の実行コードは現在のスタック位置（＝スタックポインタ）を基準に処理しますから、たくさんある処理場所を間違えることはありません。 >あっ,もしかしてこのプログラムと言うのは 終了条件が１回でも成立したあとは、必ず DrawCurve は return するということであれば、そのようになるのではないかと思います。 >あ～っもしかしてymmasayanさんが説明してくださった事はこういう事だったのでしょうか？ どうやら、そのようですね（＾＾）
お礼
お蔭様で謎が解けました^^ ついでに今まで分からなかったクイックソートの動作原理(ソートの順序)も 理解する事ができました。(感動しました！素晴らしいです^^) スタックで関数の呼び出しがされるという事が分かった事が 一番大きいと思います。 本当にありがとうございました。またご指導よろしくお願いします^^
- ymmasayan
- ベストアンサー率30% (2593/8599)
今、その問題が手元にありませんので、的確な答えは出来ませんが。 ＞ 再帰を間違って解釈してるのだと思います。 そうではなくて、解釈が不足しているだけだと思います。再帰の場合、無限ループに陥るように見えますが、途中で必ず脱出できるようにしてあります。 おそらく［/** 途中省略 **/］の部分に脱出条件が書いてあると思います。 再帰は次のような、横に展開した絵を書くとわかりやすいです。 Ｄと省略しています。前、後はＤの中のＤ２つをどけた前半部、後半部のつもり。 メイン－Ｄ前－Ｄ（１）前－Ｄ（１）前－Ｄ（１）脱出 Ｄ（２）前－Ｄ（１）脱出 Ｄ（２）脱出 Ｄ（２）後 Ｄ（１）後 Ｄ（２）前－Ｄ（１）脱出 Ｄ（２）脱出 Ｄ（２）後 Ｄ（１）後 Ｄ（２）前－Ｄ（１）脱出 Ｄ（２）脱出 Ｄ（２）後 Ｄ後 メイン 脱出と言うところで、次々と撤退が起こっていく様子がつかめると思います。 うまく揃いませんので整頓してから見てください。
お礼
お蔭様で無事疑問点が解決する事ができました。^^ 今後もご指導よろしくお願いします。
補足
ymmasayanさん早速のご返事どうもありがとうございます。 >おそらく［/** 途中省略 **/］の部分に脱出条件が書いてあると思います。 全くその通りで/** 途中省略 **/の中にreturnが入ってます。 私が勝手に関係ないと思い込んでしまったため途中で省略してしまいました。 下のが/** 途中省略 **/の部分を付け足したものです。 void DrawCurve(int sx, int sy, int x1, int y1, int x2, int y2, int ex, int ey, int len){ int p1x, p1y, p2x, p2y, p3x, p3y; int p4x, p4y, p5x, p5y, p6x, p6y; if ( CmpLine( sx, sy, x1, y1, len ) && CmpLine( x1, y1, x2, y2, len ) && CmpLine( x2, y2, ex, ey, len ) ) { MoveTo( sx, sy ); LineTo( x1, y1 ); LineTo( x2, y2 ); LineTo( ex, ey ); return ; } p1x = (sx + x1) / 2; p1y = (sy + y1) / 2; p2x = (x1 + x2) / 2; p2y = (y1 + y2) / 2; p3x = (x2 + ex) / 2; p3y = (y2 + ey) / 2; p4x = (p1x + p2x) / 2; p4y = (p1y + p2y) / 2; p5x = (p2x + p3x) / 2; p5y = (p2y + p3y) / 2; p6x = (p4x + p5x) / 2; p6y = (p4y + p5y) / 2; DrawCurve(sx, sy, p1x, p1y, p4x, p4y, p6x, p6y, len); /* ↑を(1)と名付けさせて頂きます */ DrawCurve(p6x, p6y, p5x, p5y, p3x, p3y, ex, ey, len); /* ↑を(2)と名付けさせて頂きます */ return ; } ＞Ｄと省略しています。 すみません。何をDと省略したのかが分からなかったです。 もう一度ご指導いただけないでしょうか。よろしくお願いします。
関連するQ&A
- pl/pgsqlで再帰呼び出しは可能でしょうか。
pl/pgsqlで再帰呼び出しは可能でしょうか。 PostgreSQLのバージョンは9.2.3です。 作成しているファンクションは正方形の中心座標を求めてInsertするものです。 指定した回数だけ、再帰的に正方形を４分割にどんどん細分化していき、 それぞれの正方形の中心座標をInsertします。 ４分割にした正方形をそれぞれ以下のように番号を振って説明します。 左上・・・(1) 右上・・・(2) 左下・・・(3) 右下・・・(4) 元の正方形を求めた後、(1)→(2)→(3)→(4)の順に再帰的にファンクションを呼び出します。 パラメータを「３回」以上にした場合は、(1)についてもまた４分割していきます。 ここで、パラメータを「１回」とした場合は、元の正方形の中心座標は当然Insertできます。 パラメータを「２回」とした場合、(1)の正方形の中心座標も求まりますが、 (1)の正方形については再帰の最終処理のため、Insert後にRETURNすることで エラーとなっているのか、１つ目の正方形のレコードも(2)の正方形のレコードも Insertされていません。 さらにはその「RETURN句」が元のファンクションすら「終了」させているようで、 (2)、(3)、(4)の正方形の処理が行われません。 このように再帰呼び出しをしたいと思っても、再帰中の処理を終わらせ、 呼び出し元に戻らせるはずのRETURN句が、一番最初のファンクションの「終了」と 理解されてしまい、pl/pgsqlでは再帰呼び出しは実現できないのでしょうか。 ファンクションのイメージは以下の通りです。 CREATE OR REPLACE FUNCTION Insert_squre( IN kaisuu INT, --再帰的に呼び出す回数 IN count INT, --再帰回数をカウント IN X1 INT, --正方形の左上の頂点のX座標 IN Y1 INT, --正方形の左上の頂点のY座標 IN X2 INT, --正方形の右下の頂点のX座標 IN Y2 INT --正方形の右下の頂点のY座標 ) RETURNS void AS $$ DECLARE /* 変数定義 */ ・・・・・ BEGIN /* 中心座標を求める */ ・・・・・ /* 中心座標をInsert */ ・・・・・ /* kaisuu=countならばRETURN */ ・・・・・ /* (1)の正方形について再帰処理 */ select Insert_squre( IN kaisuu INT, --再帰的に呼び出す回数 IN count+1 INT, --再帰回数をカウント IN X1 INT, --正方形の左上の頂点のX座標 IN Y1 INT, --正方形の左上の頂点のY座標 IN X3 INT, --正方形の右下の頂点のX座標 IN Y3 INT --正方形の右下の頂点のY座標 ); /* (2)の正方形について再帰処理 */ ・・・・・ /* (3)の正方形について再帰処理 */ ・・・・・ /* (4)の正方形について再帰処理 */ ・・・・・ RETURN; END; $$ LANGUAGE PLpgSQL;
- 締切済み
- PostgreSQL
- 再帰呼び出し
アッカーマン関数の値を出力するプログラム #include void main(void); int ack(int,int); void main(void) { int x,y,i; printf(" data(x) = "); scanf("%d",&x); printf(" data(y) = "); scanf("%d",&y); i = ack(x,y); printf("Ackerman = %d\n",i); } int ack(int a,int b) { int k; if (a == 0) k = b+1; else if (b == 0) k = ack(a-1,1); else k = ack(a-1,ack(a,b-1)); return (k); } この関数を呼び出した回数も出力するようにしたいのですが、どうしたらいいのでしょうか？
- ベストアンサー
- C・C++・C#
- 四角形の対角点 no2
老害と算数嫌いで・・・ ベーシックコードで ２点間(sx,sy)～(ex,ey)を対角線とする正四角形です。 他の点 (x0,y0),(x1,y1)を求めるコードを教えてください。
- ベストアンサー
- Visual Basic
- 再帰呼び出しについて（基本）
#include <stdio.h> void dan(int i); void kuku(void); void dan(int i) { int j; for (j = 1; j <= 9; j++) printf("%3d", i*j); putchar('\n'); } void kuku(void) { int i; for (i = 1; i <= 9; i++) dan(i); } int main(void) { kuku( ); return(0); } というプログラムがあるのですが、danとkukuを再帰呼び出しにしたいのですが、再帰の仕方がまったく分かりません。 知り合いに聞くと、両関数の引数を１つずつ増やすとよいと言われたのですが、手をつけられない状態です。 よろしくご教授お願いします。
- ベストアンサー
- C・C++・C#
- 再帰呼び出しの計算量
再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます． xのn乗を再帰呼び出しを用いて求める関数に関して，計算量を求める問題なのですが，どのような方針で求めればよいのでしょうか？ int exponent(int x, int n) { if(n == 0){ return 1; }else{ return x * exponent(x, n-1); } } exponentがn回呼ばれるからO(n)というのは間違いでしょうか？
- ベストアンサー
- C・C++・C#
- c言語の再帰で(関数呼び出し)+1がわからない
再帰がどのように処理されているのか理解するために、再帰の時に +1 してみたところ 0! = 1 1! = 2 2! = 5 3! = 16 4! = 65 5! = 326 6! = 1957 7! = 13700 8! = 109601 9! = 986410 10! = 9864101 となりました。 普通の階乗の値を求めた最後に +1され、それが戻されると思ったのですが違いました。 これはどういう処理がされているのでしょうか？ #include <stdio.h> int kaijo(int); int main() { int i; for (i = 0; i < 11; i++) printf("%d! = %d\n", i, kaijo(i)); return 0; } int kaijo(int n) { if (n == 0) return 1; else return n * kaijo(n - 1) + 1; }
- 締切済み
- C・C++・C#
- メソッドの再帰呼び出しについて
再帰処理に関する質問をさせていただきます。私は今複数のarraylistの中に入っているオブジェクトを順列を用いてすべての並びを所得するプログラムを作っています。プログラムが長く汚いので(汗)、例で示させていただきます。 (例) ArrayList t1; ArrayList t2; t1の中身[obj1,obj2] t2の中身[obj3,obj4] 結果:以下のように４つオブジェクトを作成 [obj1,obj3],[obj1,obj4],[obj2,obj3],[obj2,obj4] それに伴い、メソッドを作り再帰呼び出しを行っているんですが、returnでメインに返りません。戻り値はvoidです。また、 return; System.out.println("check"); と書くと、checkが出力されてしまっています(しかも何個も)。IndexOutOfBoundsExceptionのエラーがでるのですが、先にreturnを処理するはずなのになぜだろうと悩んでいます。 return以外にメインに戻る方法はあるんでしょうか？またreturnでメインに戻らない理由を知っている方がいるなら、ぜひ教えていただきたいです。よろしくお願いします。
- 締切済み
- Java
- 再帰プログラム
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); } else return 0; } return 1 + rstrlen (p);の部分で再帰をし１をプラスすることにより文字数をカウントしmainのprintfで文字数を表示しているのですがカウントしている値はどこに格納していてどのようにmainに返しているのかが分かりませんでした。教えてください。
- ベストアンサー
- C・C++・C#
- 関数の再帰処理
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657... という数列（フィボナ数列）を再帰処理でだしたいのですが・・・・・ include <stdio.h> int function( int ); int main( void ){ int n; do { printf( "0 以上の整数値を入力して下さい→ " ); scanf( "%d", &n ); }while ( n < 0 ); printf( "計算結果： %d\n", function( n ) ); getchar(); getchar(); return 0; } int function( int n ){ //フィボナの処理（function）の再帰呼び出しによる } function内に再帰処理を用いてprintf( "計算結果： %d\n", function( n ) );で画面出力したいのですが・・・・・・。
- ベストアンサー
- C・C++・C#
- 再帰について（C言語）
今、再帰処理を勉強しています。 しかし、以下のプログラムがどうしても理解できません。 流れ的には一体どういう手順になっているのでしょうか？ return i * fact( i - 1 )の部分を考えると頭が こんがらがってしまいます。 #include <stdio.h> int main( void ){ printf("５の階乗は %d です", fact(5) ); return 0; } int fact( int i ){ if( i == 1 ) return 1; else return i * fact( i - 1 ); } --------実行結果---------- ５の階乗は 120 です
- ベストアンサー
- C・C++・C#
補足
SpiralGalaxyさんご返事どうもありがとうございます。 ＞のどこかに条件判定文か何かで return してないでしょうか？ 全くその通りで,SpiralGalaxyさんのご指摘どおり省略部にはreturn;がありました。 ＞分かっていらっしゃったとしたら、お節介かも知れませんが、これは先頭に戻るわけではありません。 お節介だなんてとんでもないです。残念ながらその様に思ってました（^^; ＞スタック上に新たな変数エリアや関数戻りアドレスなどが確保され関数が実行されます。 ＞だから同じ int p1x という名前の変数でも再入の回数分の複数の実体が存在することになります。 なるほど,関数は呼び出されるとスタックに確保されると聞いた事があります。 ここで言われているのは入れ子の関数は全て違う関数として呼び出されるという事ですよね？ つまり入れ子の中の奥の関数がスタックの一番上に来るので一番最初にreturnを返すという事だと思います。 あっ,もしかしてこのプログラムと言うのは まず(1)が再帰を繰り返し(1)-(1)-(1)-(1)-(1)・・・(1)と入れ子が続いて,いつしか if (真){ return ; } となり一番奥の入れ子(1)からreturnを返していき,最後に一番手前の(1)のreturnを返し終わった後 (2)に入り再帰を繰り返し(2)-(2)-(2)-(2)-(2)・・・(2)と入れ子が続いて,いつしか if (真){ return ; } となり一番奥の入れ子(2)からreturnを返していき,最後に一番手前の(2)のreturnを返し終わった後 DrawCurve関数のreturnを返してDrawCurve関数が終わるという事でしょうか？ あ～っもしかしてymmasayanさんが説明してくださった事はこういう事だったのでしょうか？