トップダウン解析について（困っています。大至急お願いしたいです。）

質問

大至急お願いしたいです。困っています。
次のプログラムで4を入力したときのトップダウン解析したいのですが

#include <stdio.h>
void recursion(int n);
int main(void)
{
-----int a;

-----printf("整数を入力:");
-----scanf("%d", &a);

-----recursion(a);
-----printf("\n");

-----return 0;
}

void recursion(int n)
{
-----if(n > 0)
-----{
----------recursion(n-1);
----------printf("%d", n);
----------recursion(n-2);
-----}
}

実行結果：1231412

この解析を行うための図は画像のようになるということですが、流れが分かりません。はじめ、4を入力するとプログラムのrecursion(n-1);よりrecursion(4-1);となり図の一番上の箱の中recursion(3)となるのはいいと思うのですが、その次はどうすればよいのでしょうか。
分かる方がいましたら回答よろしくお願いします。

画像について（流れ）
(a) recursion(3)
(b) 4を出力
(c) recursion(2)

回答No.1

sgwjn · ベストアンサー

処理の流れは図の枠内に書いてある(1)～(3)の通りです。

recursion(4)は内部でrecursion(3)を呼出していますので、図で言うと一番上の箱の左下の箱を呼出すことになります。
で、recursion(3)は内部でrecursion(2)を呼出し…、というのをrecursion(0)が実行されるまで繰り返します。
recursion(0)は、一番左下の網掛けの箱です。
recursion関数は引数が0以下だと何も処理を行わないので無視します。

recursion(0)の実行が終了すると、recursion(0)を呼出したrecursion(1)のprintf関数が実行されます。
printf関数は、図中では■と数字で表されています。
printf関数の実行が終了するとrecursion(-1)が実行されますが引数が0以下なので何も実行されません。

これでrecursion(1)の実行が終了しますので、次はrecursion(1)を呼出したrecursion(2)のprintf関数が実行されます…

とまあ、こんな風に全部の箱を回っていくわけです。

図中の■内の数字が実行結果の出力なので、箱を回る順番は 1231412 です。
具体的には、網掛けの箱を除いて以下の順番で出力処理が実行されています。

(1) 一番左下の■1の箱
(2) (1)の一つ上の■2の箱
(3) (2)の一つ上の■3の箱
(4) (3)の右下の■1の箱
(5) (3)の一つ上の■4の箱
(6) (5)の右下の■2の箱
(7) (6)の左下の■1の箱

お礼

正確な表示の順番を理解できました。ありがとうございました。

回答No.3

sgwjn

#01です。
訂正です。

○誤
(6) (5)の右下の■2の箱
(7) (6)の左下の■1の箱

○正
(6) (5)の右下の■2の箱の左下の■1の箱
(7) (6)の一つ上の■2の箱

回答No.2

redfox63

4を入力すると mainの中のrecursion(a);により
関数recursionが引数を4として呼ばれます

関数recursionは 引数nが正(つまり1以上)であれば引数を1減じたものを引数として自分自身を呼び出します
つまりrecursion(n-1)の記述によりrecursion(3) ... 3) が実行されます
同様に recursion(n-1)の記述によりrecursion(2) ... 2)
recursion(n-1)の記述によりrecursion(1) ... 1)
recursion(n-1)の記述によりrecursion(0)
まで 再帰が実行されていきますが recursion(0)で呼ばれた段階で
if(n>0) の記述により何もしないで 1)の時点へ戻ります
ここで次の printf(%d\n",n)を実行するので『1』が出力されます
その次がrecursion(n-2)ですので これで呼ばれたrecursion(-1)は何もしません
この2点が 図の左下 空白部分にあたります
recursion(1)で呼び出された内容はすべて実行したので 2)へ戻ります
ここで printf/recursion(2-2)を実行して 3)へ戻る
といった具合に実行されていくのですよ

お礼

丁寧な解説、ありがとうございました。詳しい流れをつかむことができました！