[c言語]再帰関数で階乗値を求めみよう!!!

C言語

今回は題名にあるような階乗の計算をします。

階乗の計算聞いたことがあって計算方法を知っている人がほとんどだと思いますが、プログラムを実装してみてと言われたら難しいかなと思います。

n!=n*(n-1)*(n-2)*,,,,,,,,,*2*1

それを今回は再帰関数という関数を用いて解決していきたいと思います。

再帰関数とは?

簡単にいうとある関数の中で、自分と同じ関数を呼び出すような関数のことです。

これまではある関数から他の関数を呼び出すことはやりましたが、今回は違いますね。

同じ関数を呼び出すのです!!!

階乗の計算

#include <stdio.h>

int f(int n){

  int x; 

  if(n==0){
    printf("関数の引数: %d\n",n);
    printf("戻り値: %d\n",1);
    return 1;
  }
  else{
    printf("関数の引数: %d\n",n);
    x=n*f(n-1);
    printf("戻り値: %d\n",x);
    return x;
  }

}

int main(void){
  int n;

  printf("n: "); scanf("%d",&n);
  printf("f(%d) = %d\n",n,f(n));

}

/* 実行結果
n: 5
関数の引数: 5
関数の引数: 4
関数の引数: 3
関数の引数: 2
関数の引数: 1
関数の引数: 0
戻り値: 1
戻り値: 1
戻り値: 2
戻り値: 6
戻り値: 24
戻り値: 120
f(5) = 120
*/

ただ、階乗の値を求めるだけじゃつまらないと思ったので、途中経過の追加で調べてみました。

みてわかると思いますが、f(n)でf(n-1)を呼び出していますね。

階乗値を求める手順を3の階乗値を求める例で考えていきましょう。

  1. f(3)によって関数fが呼び出される。この関数は仮引数が3なので、3*f(2)を返却する。この乗算をするためには、f(2)の値必要なので、f(2)を呼び出す。
  2. 呼び出されたf(2)は仮引数は2なので、2*f(1)を返却する。この乗算をするためには、f(1)の値が必要なので、f(1)を呼び出す。
  3. 呼び出されたf(1)は仮引数は1なので、1*f(0)を返却する。この乗算をするためには、f(0)の値が必要なので、f(0)を呼び出す。
  4. 呼び出されたf(0)は仮引数が0なので、整数値1を返却する。
  5. 返却された値1を受け取った関数fは、1*f(0)すなわち1*1を返却する。
  6. 返却された値1を受け取った関数fは、2*f(1)すなわち2*1を返します。
  7. 返却された値1を受け取った関数fは、3*f(2)すなわち3*2を返します。

これで3の階乗値が得られます。

再帰関数を利用しない階乗値の計算

今回は再帰関数をテーマにしていたので、再帰関数を利用していきましたが再帰関数を利用するときは解くべき問題や計算すべき関数、あるいは処理するすべきデータ構造が再帰的に定義されているときです。

したがって、再帰的手続きによって階乗値を求めるのは、再帰の原理を理解するための例であって、現実的は適切ではありません。

while文と再帰関数を利用した場合だと処理の時間がかなり違います。

今回はnがとても小さい場合を実行結果に載せましたが、nが大きくなるにつれ処理時間にかなり差がついてきます。

再帰関数を利用した場合はかなり時間がかかり、while文の場合は早く処理が行われます。

なので階乗値を求めるときはwhile文などの繰り返し文を使うようにしましょう。

以上で終了となります。ありがとうございました。

コメント

タイトルとURLをコピーしました