こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

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;
}

投稿日時 - 2018-09-21 10:10:22

QNo.9539421

困ってます

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(4)

ANo.4

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

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

ですね。
失礼しました。

投稿日時 - 2018-09-21 11:06:24

ANo.3

> 普通の階乗の値を求めた最後に +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を加えた結果を基に計算する」ようになってるんで、これは既に階乗計算ではなくなっていますね。

投稿日時 - 2018-09-21 10:59:49

ANo.2

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

投稿日時 - 2018-09-21 10:49:00

ANo.1

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

投稿日時 - 2018-09-21 10:23:13

あなたにオススメの質問