• 締切済み

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

あ、ごめんなさい、タイポしてました。 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

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

  • o_chi_chi
  • ベストアンサー率45% (131/287)
回答No.2

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

  • OKWavex
  • ベストアンサー率22% (1222/5383)
回答No.1

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

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 再帰について（C言語）

    今、再帰処理を勉強しています。 しかし、以下のプログラムがどうしても理解できません。 流れ的には一体どういう手順になっているのでしょうか？ return i * fact( i - 1 )の部分を考えると頭が こんがらがってしまいます。 #include <stdio.h> int main( void ){ 　printf("５の階乗は %d です", fact(5) ); 　return 0; } int fact( int i ){ 　if( i == 1 ) return 1; 　else return i * fact( i - 1 ); } --------実行結果---------- ５の階乗は 120 です

  • 関数の再帰処理

    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657... という数列（フィボナ数列）を再帰処理でだしたいのですが・・・・・ include <stdio.h> int function( int ); int main( void ){ int n; do { printf( "0 以上の整数値を入力して下さい→ " ); scanf( "%d", &n ); }while ( n < 0 ); printf( "計算結果： %d\n", function( n ) ); getchar(); getchar(); return 0; } int function( int n ){ //フィボナの処理（function）の再帰呼び出しによる } function内に再帰処理を用いてprintf( "計算結果： %d\n", function( n ) );で画面出力したいのですが・・・・・・。

  • Ｃ言語について

    次のような問題です。 問　自然数ｎを入力し、ｎを3で割って割り切れるかどうかを判定し結果を表示する。「割り切れる」、「１余る」、「「２余る」のいずれかが入るものとする。 このようなものをつくりました。 #include<stdio.h> int main(void) { int n; printf("自然数:"); scanf("%d",&n); if(n==0){ printf("割り切れる\n"); }else if(n==1){ printf("１余る\n"); }else{ printf("２余る"); } return(0); } これで合っているかよろしくお願いします。

  • c言語のフローチャートについての質問です

    #include <stdio.h> int main (void) { int n; for (n=1900; n<2000; n++) { if (n%4==0 && n%100!=10) printf ("%d",n); else if(n%400==0) printf ("%d",n); } printf("\n"); return 0; } をどなたかフローチャートに直してください JIS規格のものでお願いします

  • c言語のフローチャートについての質問です

    #include <stdio.h> int main (void) { int n; for (n=1900; n<2000; n++) { if (n%4==0 && n%100!=10) printf ("%d",n); else if(n%400==0) printf ("%d",n); } printf("\n"); return 0; } をフローチャートに直したいのですがいまいち方法が解りません、どなたか詳しい回答お願いします JIS規格のものでお願いします

  • C言語のIF関数のアドバイスお願いします。

    #include <stdio.h> int main(){ int x,i,div=0; printf("x="); scanf("%d",&x); for(i=1;i<=x;i++){ if(x%i == 0){ div++; } } if(ここがわかりません) printf("%dは素数です\n",x); else printf("%dは素数でありません\n",x); return 0; }

  • C言語で分からないところがあるのですが……

    C言語で分からないところがあるのですが…… すみません。C言語の課題で分からないところがあり、質問しに来ました。 ユーザから数を受けて、そこまでのフィボナッチ数列を表示させるというプログラムです。 下のソースコード（でいいんですよね？）は正しいやつです。 for文を使って、繰り返しの作業を行うことに成功しましたが、doとwhileに書き換える作業がうまくできません。 どなたか助けてください。 #include<stdio.h> fib(int n) { if(n == 1)return(1); else{ if(n == 2) return (1); else return fib(n-1) + fib(n-2); } } main() { int n, i ; printf("INPUT the number.　: "); scanf("%d",&n); for(i=1; i<=n; i++){ printf("F%d = %d\n",i, fib(i)); } }

  • プログラムについて（Ｃ言語）

    #include<stdio.h> int main() { int i,n,total; for(;;){ /* 無限ループ*/ printf("整数n?"); /* nの値の表示 */ scanf("%d",&n); /* ifとbreakを使った終了判定 */ if(n<0)break; total=1; for(i=1;i<=n;i++){ printf("i=%d ",i); total*=i; /* total←total*i(階乗の計算) */ } printf("total=%d\n",total); /* totalの値(結果)の表示 */ } printf("Thanks\n"); /* 終了メッセージの表示 */ return(0); } これは階乗を求めるプログラムなのですが、i++ではなくi--をつかって求める場合 どのように変更すればよいでしょうか？ for(i=1;i<=n;i++){ あたりをいろいろ弄ってみたのですが、求めてる結果は得られませんでした

  • 組み合わせ

    n個の集合からp個を取る組み合わせの総数を出力するプログラムなんですが nCp=n!/p!(n-p)!という式を使い #include<stdio.h> int kaijo(int m); int comb(int n,int p); int main(void) { int i,j; printf("n="); scanf("%d",&i); printf("p="); scanf("%d",&j); printf("comb(%d,%d)=%d\n",i,j,comb(i,j)); } int kaijo(int m) { if(m>0) return(m*kaijo(m-1)); else return 1; } int comb(int n,int p) { if(n>0) return((n*kaijo(n-1))/(p*kaijo(p-1)*(n-p)*kaijo(n-p-1))); else return 1; } と書いてみたのですがこれではnが大きいとＣ言語のint型で扱える最大値を超えてしまい正しい結果が出力されません。 　そこでint型を使ったままでnやpが大きい場合でもある程度出力できるようにしたいのですがどう改良したらよいのでしょうか？ おそらくnCp=n*(n-1)*・・・*(n-p+1)/p!という式を使うのですがよく分かりません。よろしくお願いします。

  • 困ってます…nCrを求めるＣ言語プログラミング

    nCr、つまりn個のうちr個を取り出すときの場合の数を求めるプログラミングを作りたいのですが、どうもうまくいきません。 関数combinationを作って求めるという指定もあり、自分で出来るとこまで作ってみたのですが訳がわからなくなってしまい、かなり困っています…； コンパイルは出来るのですが実行してもセグメントエラーが出るばかりで… すみませんがご指摘していただけないでしょうか…？ #include<stdio.h> //階乗を計算する関数 int fact(int num){ int i; if(num < 0){ return -1; } else if(num == 0){ return 1; } else if(num == 1){ return 1; } else { i = num * fact(num - 1); return i; } } //コンビネーションを計算 int combination(int n, int r) { int fact(int num); int i; i=fact(n)/fact(r)/fact(n-r); return combination(n-1, r-1)-combination(n,r-1); } int main(void) { int n, r; while ( printf("n r を入力して下さい。"), scanf("%d%d", &n, &r) == 2 ) { printf("nCr(%d,%d)=%d\n", n, r, combination(n, r)); } return 0; }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する