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)の処理に行くのでしょうか?
再帰を間違って解釈してるのだと思います。
ご存知の方どうか教えてください。よろしくお願いします。
No.2ベストアンサー
- 回答日時:
>/** 途中省略 **/
のどこかに条件判定文か何かで return してないでしょうか?本当にこのままだとしたらスタックがオーバーフローするので一瞬のうちにプログラムがコケるはずです。
>(1)の処理に入ったらDrawCurve関数の先頭に行くと思うのですが,
分かっていらっしゃったとしたら、お節介かも知れませんが、これは先頭に戻るわけではありません。スタック上に新たな変数エリアや関数戻りアドレスなどが確保され関数が実行されます。だから同じ int p1x という名前の変数でも再入の回数分の複数の実体が存在することになります。
>それとも(1)の後(2)の処理に行くのでしょうか?
>再帰を間違って解釈してるのだと思います。
/** 途中省略 **/ 部分に return がない限り(2)には行かないと思います。
この回答への補足
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さんが説明してくださった事はこういう事だったのでしょうか?
No.3
- 回答日時:
>なるほど,関数は呼び出されるとスタックに確保されると聞いた事があります。
>ここで言われているのは入れ子の関数は全て違う関数として呼び出されるという事ですよね?
「全て違う関数として呼び出される」というのは、正しいといってもよいのではないかと思います。
ただ関数そのものの実行コードは1ヶ所にしかありません。再入を繰り返すと関数自体がたくさんできるわけではなくて、その処理場所がたくさんできることになります(=自動変数の保存場所、関数の戻りアドレス保存場所など)。関数の実行コードは現在のスタック位置(=スタックポインタ)を基準に処理しますから、たくさんある処理場所を間違えることはありません。
>あっ,もしかしてこのプログラムと言うのは
終了条件が1回でも成立したあとは、必ず DrawCurve は return するということであれば、そのようになるのではないかと思います。
>あ~っもしかしてymmasayanさんが説明してくださった事はこういう事だったのでしょうか?
どうやら、そのようですね(^^)
お蔭様で謎が解けました^^
ついでに今まで分からなかったクイックソートの動作原理(ソートの順序)も
理解する事ができました。(感動しました!素晴らしいです^^)
スタックで関数の呼び出しがされるという事が分かった事が
一番大きいと思います。
本当にありがとうございました。またご指導よろしくお願いします^^
No.1
- 回答日時:
今、その問題が手元にありませんので、的確な答えは出来ませんが。
> 再帰を間違って解釈してるのだと思います。
そうではなくて、解釈が不足しているだけだと思います。再帰の場合、無限ループに陥るように見えますが、途中で必ず脱出できるようにしてあります。
おそらく[/** 途中省略 **/]の部分に脱出条件が書いてあると思います。
再帰は次のような、横に展開した絵を書くとわかりやすいです。
Dと省略しています。前、後はDの中のD2つをどけた前半部、後半部のつもり。
メイン-D前-D(1)前-D(1)前-D(1)脱出
D(2)前-D(1)脱出
D(2)脱出
D(2)後
D(1)後
D(2)前-D(1)脱出
D(2)脱出
D(2)後
D(1)後
D(2)前-D(1)脱出
D(2)脱出
D(2)後
D後
メイン
脱出と言うところで、次々と撤退が起こっていく様子がつかめると思います。
うまく揃いませんので整頓してから見てください。
この回答への補足
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と省略しています。
すみません。何をDと省略したのかが分からなかったです。
もう一度ご指導いただけないでしょうか。よろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C++ bmp 透過処理
-
迷路を脱出する経路探索プログ...
-
C言語で%を使わない余りの出し方
-
再起呼び出しの回数をカウント...
-
| (or) を使った関数の引数の作...
-
異なるn個の整数からr個の整数...
-
OpenCVによる4値化について
-
【C#】SQL文の中に変数を埋め込...
-
3のつく数と3の倍数を表示 C言語
-
c言語プログラミングについて f...
-
C++デバックエラーについて詳し...
-
argvのNULLチェック
-
intとlongは同じ?
-
ライントレース:C言語 物理セン...
-
論理演算結果の表示について
-
最大の四角形を求めるプログラム
-
これらの意味は?
-
C++で表を作成したいのです ...
-
2の補数を計算するプログラム
-
偶数パリティ
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
2の補数を計算するプログラム
-
intとlongは同じ?
-
C言語で簡単なパックマンゲーム...
-
迷路を脱出する経路探索プログ...
-
関数とビット列
-
3のつく数と3の倍数を表示 C言語
-
再起呼び出しの回数をカウント...
-
OpenCVによる4値化について
-
C++で表を作成したいのです ...
-
コマンドプロンプトのウィンド...
-
再帰処理をループ処理に変換
-
画像の拡大・縮小
-
プログラミングに関して
-
【C#】SQL文の中に変数を埋め込...
-
分数の足し算をさせるプログラ...
-
argvのNULLチェック
-
C言語で%を使わない余りの出し方
-
whileとifを使い偶数を出すには
-
ヌメロンのプログラム
-
条件が多い場合
おすすめ情報