c言語の再帰で(関数呼び出し)+1がわからない

質問

再帰がどのように処理されているのか理解するために、再帰の時に +1 してみたところ
0! = 1
1! = 2
2! = 5
3! = 16
4! = 65
5! = 326
6! = 1957
7! = 13700
8! = 109601
9! = 986410
10! = 9864101
となりました。
普通の階乗の値を求めた最後に +1され、それが戻されると思ったのですが違いました。
これはどういう処理がされているのでしょうか？

#include <stdio.h>

int kaijo(int);

int main()
{
int i;
for (i = 0; i < 11; i++)
printf("%d! = %d\n", i, kaijo(i));
return 0;
}

int kaijo(int n)
{
if (n == 0)
return 1;
else
return n * kaijo(n - 1) + 1;
}

回答No.4

cametan_42

あ、ごめんなさい、タイポしてました。

kaijo(3) = 3 * kaijo(2) + 1 = 3 * (kaijo(1) + 1) + 1 = 15 + 1 = 16
kaijo(4) = 4 * kaijo(3) + 1 = 4 * (kaijo(2) + 1) + 1 = 64 + 1 = 65
kaijo(5) = 5 * kaijo(4) + 1 = 5 * (kaijo(3) + 1) + 1 = 325 + 1 = 326

ですね。
失礼しました。

回答No.3

cametan_42

> 普通の階乗の値を求めた最後に +1され、それが戻されると思ったのですが違いました。
> これはどういう処理がされているのでしょうか？

つまり、

int kaijo(int n)
　　{
　　　　if (n == 0)
　　　　　　return 1;
　　　　else
　　　　　　return n * kaijo(n - 1) + 1;
　　}

は「普通の階乗の値を求めた最後に +1」してる関数じゃないから、です。
細かく見ると、n == 1以外の処理が再帰になってるわけですが、

return n * kaijo(n - 1) + 1;

ここで呼び出されてる kaijo(n - 1) が既に普通の階乗計算じゃありません。

kaijo(0) = 1

はベースケースとして良いとして、

kaijo(1) = 1 * kaijo(0) + 1 = 1 + 1 = 2

となる。
次は

kaijo(2) = 2 * kaijo(1) + 1 = 2 * ( kaijo(0) + 1) + 1 = 4 + 1 = 5

そして、

kaijo(3) = 3 * kaijo(2) + 1 = 3 * (kaijo(2) + 1) + 1 = 15 + 1 = 16
kaijo(4) = 4 * kaijo(3) + 1 = 4 * (kaijo(3) + 1) + 1 = 64 + 1 = 45

....

と「再帰呼び出しされる度にkaijo(n-1)に1を加えた結果を基に計算する」ようになってるんで、これは既に階乗計算ではなくなっていますね。

回答No.2

o_chi_chi

２の場合
2*kaijo(1)+1
⇒2*(1*kaijo(0)+1)+1　
⇒2*(1*(1)+1)+1
なので
2*2+1=5
です

回答No.1

OKWavex

kaijo(n-1)をn倍して1をたす