階乗のプログラムの出力の流れがよくわかりません。

Question

int fact(int n)
{
int x ;
printf("n=%d\n",n);
if (n == 0) return 1;
else x=fact(n-1);
printf("fact(%d)=%d\n", n-1, x);
return fact(n-1)*n ;
}

int main(void)
{
  printf("ans=%d",fact(4));
  return 0;
}

n=4
n=3
n=2
n=1
n=0
fact(0)=1
n=0
fact(1)=1
n=1
n=0
fact(0)=1
n=0
fact(2)=2
n=2
n=1
n=0
fact(0)=1
n=0
fact(1)=1
n=1
n=0
fact(0)=1
n=0
fact(3)=6
n=3
n=2
n=1
n=0
fact(0)=1
n=0
fact(1)=1
n=1
n=0
fact(0)=1
n=0
fact(2)=2
n=2
n=1
n=0
fact(0)=1
n=0
fact(1)=1
n=1
n=0
fact(0)=1
n=0
ans=24

上の再帰関数を使って階乗を計算するプログラムなのですが出力結果が下に書いてある様になるのがよくわかりません。

私の考えは、

n=4
n=3
n=2
n=1
n=0
fact(3)=6
fact(2)=2
fact(1)=1
fact(0)=1
ans=24

となると思うのですがなぜ上の様になってしまうのでしょうか？
プログラムの流れを教えていただけたら幸いです。

Answer 1

fact(n-1)を2回呼んでいるからです。

2回目のreturn fact(n-1)*n;をreturn x*n;に変えれば、お書きのようになるはずです。

Comments

[satakehirohumi]

なるほど！
1回目のx=fact(n-1)を自分の解答だと呼び出せていないのですね。

[episteme]

呼び出せてないんじゃなく、
その結果を無視して(return時に)再度fact(n-1)してるから、都合2回呼んでしまってる。