C言語の関数再帰に関する疑問

Question

初学者で申し訳ないです。
関数の再帰に関して、コード内の命令が実行される順序について質問します。

• コード

#include <stdio.h>

void wand(int n)
{
	printf("in %d\n", n);
	if (n > 1)
		wand(n - 1);
	printf("out %d\n", n);
}

int main(void)
{
	wand(3);

	getchar();
	return 0;
}

• 実行結果

in 3
in 2
in 1
out 1
out 2
out 3

in の出力が終わった後にout が1,2,3と連続して出力されたのはなぜでしょうか。
上から下へプログラムが実行されるとすれば、in 1 の次は out 1 で止まると思っていたのですが…。

• 環境

Visual Studio Community 2017

Answer 1

ホワイトボードの出番だ。
呼びだされた関数が return すると、処理は呼び出した次の箇所に戻ることを思い出してください。すると処理の流れはこのようになります。

Answer 2

out 1の出力後の次の実行位置は、呼び出し元のwand(n - 1);の次の行であるためです。
再帰呼び出しを以下のように展開してみれば理解できると思います。

wand(int n) // n = 3
{
    printf("in %d\n", n); // n = 3
    wand(int n) // n = 2
    {
        printf("in %d\n", n); // n = 2
        wand(int n) // n = 1
        {
            printf("in %d\n", n); // n = 1
            printf("out %d\n", n); // n = 1
        }
        printf("out %d\n", n); // n = 2
    }
    printf("out %d\n", n); // n = 3
}

Comments

[jegan]

なるほど、入れ子のような形になった結果なのですね！
直感的に理解できました。ありがとうございます。

[jegan]

他の方も、丁寧に回答してくださり助かりました。

Answer 3

こんにちは。
SHOMIさんのご説明にある通り、実行順に処理を辿ると理解できると思います。
0. inのprintf実行
0. wandが呼び出される（最初の再帰）
0. （最初の再帰の）inのprintf実行
0. wandが呼び出される（２度目の再帰）
0. （２度目の再帰の）inのprintf実行
0. wandが呼び出される（３度目の再帰）
0. （３度目の再帰の）inのprintf実行
0. n == 1なので再帰しない
0. （３度目の再帰の）outのprintf実行
0. （３度目の再帰から）リターン
0. （２度目の再帰の）outのprintf実行
0. （２度目の再帰から）リターン
0. （最初の再帰の）outのprintf実行
以上