締切済み

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

  • 困ってます
  • 質問No.9539421
  • 閲覧数141
  • ありがとう数4
  • 気になる数0
  • 回答数4
  • コメント数0

お礼率 39% (102/259)

再帰がどのように処理されているのか理解するために、再帰の時に +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;
}

回答 (全4件)

  • 回答No.4

ベストアンサー率 61% (148/239)

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

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

ベストアンサー率 61% (148/239)

> 普通の階乗の値を求めた最後に +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

ベストアンサー率 45% (131/287)

2の場合
2*kaijo(1)+1
⇒2*(1*kaijo(0)+1)+1 
⇒2*(1*(1)+1)+1
なので
2*2+1=5
です
  • 回答No.1

ベストアンサー率 22% (1220/5379)

他カテゴリのカテゴリマスター
kaijo(n-1)をn倍して1をたす
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する

特集


OKWAVE若者応援スペシャル企画

ピックアップ

ページ先頭へ