非末尾再帰について

質問

非末尾再帰を理解しようとすごく簡単なプログラムを書いてみたのですが、
どのように動作しているのかいまいち分かりません。
プログラムは以下のようなものです。
void rec(int n);
int main(){
int n = 3;
rec(n);
}

void rec(int n)
{
cout<<"AAA"<<n<<endl;
if(n > 0){
n--;
cout<<"BBB"<<n<<endl;
rec(n);
}
cout<<"CCC"<<n<<endl;
}

実行すると、出力は以下のようになりました。
AAA3
BBB2
AAA2
BBB1
AAA1
BBB0
AAA0
CCC0
CCC0
CCC1
CCC2

１回目のCCC0までは理解できますが、
そのあとなぜCCC0、CCC１、CCC2となるのか
分かりません。
そこが内部でどのように動作しているのか
説明していただけるとありがたいです。

回答No.1

hidebun · ベストアンサー

よくわからないときは、関数の中身を展開して考えましょう。
下記は、インデントが崩れてますが、エディタなどにコピーして確認してください。
関数の呼び出しが完了すると、呼び元に戻ります。
指でなぞりながら処理の流れを追うとわかると思います。

main()
　n=3
　rec(3)
　　　AAA3
　　　BBB2
　　　rec(2)------rec(2)
　　　CCC2　　　　AAA2
　　　　　　　　　BBB1
　　　　　　　　　rec(1)--------rec(1)
　　　　　　　　　CCC1　　　　　AAA1
　　　　　　　　　　　　　　　　BBB0
　　　　　　　　　　　　　　　　rec(0)--------rec(0)
　　　　　　　　　　　　　　　　CCC0　　　　　AAA0
　　　　　　　　　　　　　　　　　　　　　　　CCC0

お礼

ありがとうございます。

図で示されていると明確で非常に分かりやすかったです。