C言語Tips集 - 階乗を計算する
C言語には階乗を計算する関数やマクロはありません．したがってプログラマが自ら階乗を求める必要があります．
階乗は定義そのものが再帰的な構造になっているため，よく再帰を学ぶためのサンプルプログラムとして用いられますが，もちろん通常のループを用いて実装することも可能です．ここでは再起を用いた実装とループを用いた実装の2つのサンプルプログラムを掲載することにします．
再帰を用いた実装
nの階乗は以下の式で求めることができます．
n! = f(n)とすると階乗は以下のような再帰構造をもつ式で表すことができます．
この式をC言語で実装すると以下のようになります．
/**
* 階乗を計算する
* @param[in] n 整数
* @return 階乗
*/
int factorial(int n) {
if (n > 0) {
return n * factorial(n - 1);
} else {
return 1;
}
}
ループを用いた実装
nの階乗は以下の式で求めることができます．
この式を右から左に見てみると階乗は1からnまでの総乗を求めればよいことがわかります．
この式をC言語で実装すると以下のようになります．
/**
* 階乗を計算する
* @param[in] n 整数
* @return 階乗
*/
int factorial(int n) {
int result = 1;
int k;
for(k = 1; k <= n; k++) {
result *= k;
}
return result;
}
C言語サンプルプログラム
以下に階乗を計算するサンプルプログラムを示します．
/* header files */
#include <stdio.h>
#include <stdlib.h>
/* functions */
int factorial_recursive(int n);
int factorial_loop(int n);
/* main */
int main(void) {
int n = 5;
int result1, result2;
result1 = factorial_recursive(n);
result2 = factorial_loop(n);
printf("%d! = %d\n", n, result1);
printf("%d! = %d\n", n, result2);
return EXIT_SUCCESS;
}
/**
* 階乗を計算する(再帰)
* @param[in] n 整数
* @return 階乗
*/
int factorial_recursive(int n) {
if (n > 0) {
return factorial_recursive(n - 1) * n;
} else {
return 1;
}
}
/**
* 階乗を計算する(ループ)
* @param[in] n 整数
* @return 階乗
*/
int factorial_loop(int n) {
int result = 1;
int k;
for(k = 1; k <= n; k++) {
result *= k;
}
return result;
}
実行例
サンプルプログラムの実行結果は以下のようになります．
5! = 120 5! = 120
Cプログラマの必読書
たくさんあるC言語関連の書籍の中でも特に役に立った本です．よかったら参考にしてみてください．
C言語の実践的参考書．少々値段は張りますが初心者を脱しようとしている人は絶対に読むべきです．
文法だけでなく，コーディングスタイルやデバッグなど文字通り「実践的」なことが書かれているので非常にためになります．
オライリーの本は，読みにくい本が多いのですが本書はとても読みやすくオススメです．
ポインタの解説書としては最高の書籍です．
この1冊でポインタを完全に理解することができます．全くの初学者が読むには敷居が高いですが，入門書を読み終えた後に読むと非常に有益です．