ハノイの塔 関数内の進み方

質問

■プログラムは後半に書いてます。よろしくお願いします。

　　　　　no x y
―――――――
10行目　3 1 3
10行目　2 1 2
10行目　1 1 3
printf

■この後の５回（できれば10回）の進み方を教え貰えると嬉しいです。

■わからない理由
printfのとき、(no, x, y) = (1, 1, 3)でno = 1。
そのため１３行目は行われない。
しかし、returnもbreakもないためまた６行目に戻るのでしょうか？（答えを見ると６行目に行きそうです。）
(no, x, y) はどのような値で関数が始まるのでしょうか？
９行目があるのにno=2or3で表示される理由がわからないです。

01|#include <stdio.h>
02|#include <conio.h>
03|
04|#define N 3
05|
06|void move(int no,int x,int y)
07|{
08| static int i=1;
09| if(no>1)
10| move(no-1,x,6-x-y);
11| printf("%dを%d軸から%d軸へ移動 : %d\n",no,x,y,i++);
12| if(no>1)
13| move(no-1,6-x-y,y);
14|}
15|
16|int main(void)
17|{
18| move(N,1,3);
19|
20| _getch();
21| return(0);
22|}

回答No.3

Tacosan · ベストアンサー

再帰を考えるときに「10行目 に行くと　n > 1　で6行目に戻りますよね？」と思っちゃダメです. #2 に書いてある「別の move」の意味を読み取ってください.

分かりやすいかどうか知らんしあんまり適切って感じもしないけど, こんな風に考えることもできます:
最初に main から呼び出される move を move0, move0 から呼び出される関数を move1, ... としてみてください. つまり

void move1(int no,int x,int y) /* (b) */
{
static int i=1;
if(no>1)
move2(no-1,x,6-x-y);
printf("%dを%d軸から%d軸へ移動 : %d\n",no,x,y,i++);
if(no>1)
move2(no-1,6-x-y,y);
}

void move0(int no,int x,int y) /* (b') */
{
static int i=1;
if(no>1)
move1(no-1,x,6-x-y); /* (a) */
printf("%dを%d軸から%d軸へ移動 : %d\n",no,x,y,i++);
if(no>1)
move1(no-1,6-x-y,y);
}

int main(void)
{
move0(N, 1, 3);
/* 以下略 */
}

のような感じです. このとき, (a) の関数呼び出しによって (b) と (b') のどちらに行くと思いますか?

「再帰呼び出し」というのは, 同じ関数を「改めて呼び出す」ということです. 間違っても「関数の先頭に戻る」という意味ではありません.

お礼

ありがとうございます。
同じ奴では無いということですね！

一段目のmove1
その次に二段目のmove1
そして三段目のmove1に・・・

なんとなく再帰理解することが出来ました。ありがとうございます。

回答No.2

kmee

これは、「再帰」と呼ばれる方法です。
関数内で自分自身を呼びだします。

moveの動作は次の通りです。
9,10行目:n>1ならmove(no-1,x,6-x-y);を呼び出す
11行目:printf
12,13行目:n>1ならもmove(no-1,6-x-y,y);を呼び出す
14行目:関数の終りなのでreturn

10行目　3 1 3
10行目　2 1 2
10行目　1 1 3
printf
とありますが、10行目でループしているのではなく、
3 1 3 mainの中からmove(3,1,3)で呼び出したもの
2 1 2 ↑のmoveの10行目で move(2,1,2)で呼び出したもの
1 1 3 ↑のmoveの10行目で move(1,1,3)で呼び出したもの
printf ↑で呼び出されたmove(1,1,3)はn=1なので、もう別のmoveは呼び出さない
と、 moveの中からmoveを呼び出したものです。

> しかし、returnもbreakもないためまた６行目に戻るのでしょうか？
戻りません。
途中で「別のmove」を実行しているので、6行目に戻っているように見えるだけです。
関数の最後まできたら自動的にreturnする、というのがCの動作です。

> (no, x, y) はどのような値で関数が始まるのでしょうか？
どこから呼ばれるかは、順番に辿ればわかります。
実行して最初に呼ばれるのはmain関数です。
その中に move(N,1,3); とあるので、これが最初です。

> ９行目があるのにno=2or3で表示される理由がわからないです。

if(no>1)
move(no-1,x,6-x-y);
ですが、 {}が無いですよね? これは、ifの直後の ; までが{}に入っているのと同じことです。
if(no>1) {
move(no-1,x,6-x-y);
}
どちらも正しい文法です。前者は初心者にはまぎらわしいので、{}を必ず付けるようにするとよいでしょう。
で、こうすると、printfには何も条件が付いていないことがわかります。

お礼

ありがとうございました。理解出来ました。

補足

■素早い返答ありがとうございますm(_ _)m

■関数の最後まできたら自動的にreturnする、というのがCの動作です。
知りませんでした！ありがとうございます！

■まだ分からない所が・・・時間があればもう一度よろしくお願いします。

10行目 に行くと　n > 1　で6行目に戻りますよね？
そうするとまた10行目・・・
となり結局11行目のprintfへたどり着くときは n = 1 以外ないような気がします。

11行目 に行けたということは n ＝ 1 と言うことで…、そうすると 12行目 の条件式の存在意味が…ない？
本当に 12行目 の式は正しいんでしょうか？

PS　この問題と課題は「解きながら学ぶC言語」に掲載されていた例題です。

回答No.1

Tacosan

返り値が void であるような関数では, 最後の } にたどりついたら「return; が書かれている」ものとして処理されます.

これで「returnもbreakもないため」という疑問は完全に解消されましたね.

お礼

ありがとうございました。理解出来ました。

補足

返り値が void であるような関数だと「return; が書かれている」ものとして処理されるんですね！
理由を知れる方が記憶に残るので・・・ありがとうございます！

よければ上の補足質問よろしくお願いしますm(_ _)m