このページでは、C言語での「階乗の求め方」について解説していきます。
負の整数を除く整数（非負の整数）である n の階乗は n! と表記され、n! は 1 〜 n までの整数を全て掛け合わせた結果となります。
n! = n * (n - 1) * (n - 2) * ・・・ * 2 * 1例えば 5! は、1 〜 5 を全て掛け合わせた結果となります。
5! = 5 * 4 * 3 * 2 * 1 = 120また、例えば 4! は、1 〜 4 を全て掛け合わせた結果となります。
4! = 4 * 3 * 2 * 1 = 24同様に、他の正の整数に関しても階乗の値を求めることが可能です。
ただし、0! の結果は 1 となります。0 ではないので注意してください。
for ループで階乗を求める
では、階乗の求める関数の紹介と、その説明をしていきたいと思います。まずは for ループで階乗を求めていきたいと思います。
階乗を計算する関数
ここまで紹介してきた n! の計算結果は、下記のような factorial 関数により求めることができます（n は関数の引数として与えられる）。
#include <stdio.h>
unsigned int factorial(unsigned int n) {
unsigned int ans;
ans = 1;
for (unsigned int i = 2; i <= n; i++) {
ans *= i;
}
return ans;
}
int main(void) {
for (unsigned int i = 0; i < 10; i++) {
printf("%u!:%u\n", i, factorial(i));
}
return 0;
}factorial 関数では、まず ans に 1 を格納してから for ループでの繰り返し処理を行なっています。
この for ループの中では、i が 2 〜 n になるまで i を 1 ずつ増やしながら下記の処理を繰り返しています。
ans *= i;上記の処理は ans = ans * i; と同じ意味の処理になります。つまり、ans * i の結果を ans に格納する処理となります。
そのため、最初に i が 2 の状態で上記が実行される際には、ans の値は 1 ですので、1 * 2 の実行結果が ans に格納されることになります。つまり、ans には 2! の結果が格納されることになります。
また、次に i が 3 の状態で上記が実行される際には、ans の値は 1 * 2 ですので、1 * 2 * 3 の実行結果が ans に格納されることになります。つまり、ans には 3! の結果が格納されることになります。
こんな感じで、上記の for ループの中で ans *= i が実行されると、ans には i! の値が格納されることになります。ですので、i が n の状態で上記が実行されるまでループを回せば、ans には n! の結果が格納されることになります。
そして、i が n + 1 になった際に for ループを抜けることになるので、n! の結果が格納された ans が返却されることになり、factorial 関数が引数 n に対する n! の結果を求めることができることになります。
また、n が 0 や 1 の場合は for ループの継続条件 i <= n を満たさないため、ループ内部の処理は一度も実行されません。そのため ans が 1 の状態で ans が返却されることになりますが、0! も 1! も結果は 1 ですので、正しく n! が求められることになります。
ちなみに、for ループにおける初期化式は i = 2 ではなく i = 1 としても正しく n! を求めることができます。ループ回数が１回増えますが、1 が余分に掛けられるだけですので factorial 関数が返却する値に変化はありません。
スポンサーリンク
間違った階乗の計算１
割と単純な処理ですが、プログラミングに慣れていないと結構間違いやすい処理でもありますので、ここで階乗を求める際によくやる間違い例をいくつか紹介したいと思います。
まず、下記の factorial 関数では正しく n! を求めることができません。
unsigned int factorial(unsigned int n) {
unsigned int ans;
for (unsigned int i = 2; i <= n; i++) {
ans *= i;
}
return ans;
}良くない点は、ans に値を格納しないまま for ループを実行してしまっているところです。前述の通り、ans *= i は ans = ans * i と同じ意味の処理になります。つまり、右辺を計算する際に ans の値が利用されることになります。
ただし、ans は変数宣言されただけで初期化や代入が行われていませんので、ans には不定値が格納されていることになります。そのため、ans *= i では不定値と i が掛けられることになり、どんな結果になるかが分からない、実行するたびに結果が変わる、という状態になってしまっています。
ans はしっかり 1 で初期化 or 1 を代入してから、for ループを実行する必要があります。
間違った階乗の計算２
また、下記の factorial 関数でも正しく n! を求めることができません。
unsigned int factorial(unsigned int n) {
unsigned int ans;
ans = 1;
for (unsigned int i = 2; i < n; i++) {
ans *= i;
}
return ans;
}for ループの継続条件が i < n になっているので、i が n になった際に ans *= i が実行されずに for ループが終了することになり、結果的に (n - 1)! の結果が求められることになってしまいます。
間違った階乗の計算３
さらに、下記の factorial 関数でも正しく n! を求めることができません。
unsigned int factorial(unsigned int n) {
unsigned int ans;
ans = 1;
for (unsigned int i = 0; i <= n; i++) {
ans *= i;
}
return ans;
}i が 0 の状態から for ループが始まるので、最初に ans *= i が実行された際に、必ず ans の値が 0 になることになります。0 に何を掛けても結果は 0 になりますので、以降何回 ans *= i が実行されても ans の値は 0 のままで、factorial の返却値も 0 になってしまいます。
スポンサーリンク
再帰関数で階乗を求める
次は、再帰関数を利用して階乗を求めていきたいと思います。
最初にも説明した通り、負の整数を除く整数である n の階乗は n! と表記され、n! は 1 〜 n までの整数を全て掛け合わせた結果となります。
n! = n * (n - 1) * (n - 2) * ・・・ * 2 * 1さらに、(n-1)! は下記により求めることができます。
(n - 1)! = (n - 1) * (n - 2) * ・・・ * 2 * 1ということは、n! は、(n - 1)! を用いて下記により求めることができることになります。
n! = n * (n - 1)!ここで、引数で指定された非負の整数の階乗を求める関数を factorial とすれば、結局 n! は下記により求めることができることになります。
factorial(n) = n * factorial(n - 1)つまり、非負の整数 n を引数とする関数 factorial は、n に factorial(n - 1) の結果を掛けた結果を返却する関数として記述することができます。
ただし、n が 0 の時は上式では求めることができず、単に n! は 1 となります。
上式の考え方を利用して作成した関数 factorial は下記のようになります。こんな感じで、関数の中から自分自身の関数を呼び出すことを、「再帰呼び出し」や「再帰処理」と呼び、再帰呼び出しを行う関数のことを「再帰関数」と呼びます。
unsigned int factorial(unsigned int n) {
if (n <= 0) {
return 1;
}
return n * factorial(n - 1);
}直感的に考えれば、factorial は引数 n に対して n! を求める関数ですので、上記の n * factorial(n - 1) は n * (n - 1)!、すなわち n! を求める処理であると理解できると思います。
ただし、引数 n が 0 や 1 の場合、つまり 1! や 0! を求める場合、必ず答えは 1 となりますので、factorial 関数を再帰呼び出しするまでもなく、return 1 を実行してしまえば良いことになります。それを行なっているのが、最初の if 文部分になります。
上記は直感的に捉えた場合の factorial 関数の動作の理解の仕方になります。
実際の動作を考えていくと、factorial 関数では下の図のように、引数を 1 つずつ小さくしながら factorial(n) から factorial(1) まで実行されることになります。
階乗を求めるのは n が大きいほど大変ですので、引数 n を 1 減らすことは、階乗の計算を行うという問題を一段階簡単にすることであると捉えることができます。なので、上の図のように引数に与える値を減らしながら再帰呼び出しを行うことで、問題を一段階ずつどんどん簡単にしていくことができます。
そして、いずれはめちゃめちゃ簡単な問題（答えが自明な問題）になります。今回の場合は factorial(1)（もしくは factorial(0)）がそれにあたります。なぜなら答えが 1 と分かりきっているからです。
この場合は、もう問題を簡単にする必要がありませんので、再帰呼び出しも行う必要がありません。そのため、引数が 1 以下の場合は再帰呼び出しを行わずに 1 を返却するよう、factorial 関数の最初部分に if 文を設けています。
これにより、どんどん再帰呼び出しされていく流れが終わり、次はどんどん関数の実行結果を return して関数を終了していく流れに変わります。いずれは factorial(n - 1) の関数も終了しますので、この factorial(n - 1) を実行した factorial(n) は、factorial(n - 1) の返却値を利用して n! の値を求めることができます。
もし、関数の最初の if 文が無ければ、延々と再帰呼び出しが繰り返し行われることになりますので注意してください（実際には途中でスタックオーバーフローが発生してプログラムが強制的に終了させられます）。
このように、再帰呼び出しを行う際には、上記の if 文のように、関数の結果が自明（今回は n が 0 や 1 の時の n! の結果が自明）になった際に、再帰呼び出しの繰り返しを止めるための条件文が必要になります。
そして、その条件に近づいていくように（関数で解く問題が一段階簡単になるように）再帰呼び出しを行う関数の引数を設定していく必要があります（今回は引数 n を 1 減らすことでいずれ引数 n が 1 になるようにしている）。この辺りが再帰呼び出しを行うポイントになると思います。
基本的に、問題を一段階簡単にする処理と、問題の答えが自明になった際に再帰呼び出しを行わないようにする処理を記述すれば良いだけなので、複雑な問題を解く関数であっても、再帰呼び出しを利用すると簡単に実装できることも多いです。
オーバーフローに注意
階乗の計算は、特にオーバーフローに注意が必要です。n を少し大きくするだけで、n! の結果がすごく大きな値になってしまいます。
例えば、n が 13 の場合、n! の結果、すなわち 13! の結果は 6227020800 となります。符号なしで考えた場合、この値を表すためには 33 ビット必要で、多くの環境で unsigned int では表現できない値となります（unsigned int のサイズが 4 バイト、すなわち 32 ビットである場合）。
for ループで階乗を求める と 再帰関数で階乗を求める で紹介した factorial 関数では共に、n! の結果を扱う変数 ans や返却値の型を unsigned int としているため、引数 n に 13 を指定した場合はオーバーフローが発生して n! の結果が正しく求められないので注意してください。具体的には、unsigned int のサイズが 4 バイトの場合、オーバーフローが発生して n! の結果が 1932053504 となってしまいます（正解は 6227020800）。
もっと大きな n の階乗結果を求めたい場合は、factorial 関数の変数 ans や返却値の型に、unsigned int よりもサイズの大きな型、例えば unsigned long や unsigned long long 型を用いる必要があります。さらに、階乗結果を printf で表示する場合は、変換指定子に %lu や %llu を指定する必要があります。
例えば、型に unsigned long を用いる場合、for ループで階乗を求める で紹介した factorial 関数および、factorial 関数を呼び出す main 関数は下記のように変更する必要があります。
#include <stdio.h>
unsigned long factorial(unsigned int n) {
unsigned long ans;
ans = 1;
for (unsigned int i = 2; i <= n; i++) {
ans *= i;
}
return ans;
}
int main(void) {
for (unsigned int i = 0; i <= 20; i++) {
printf("%u:%lu\n", i, factorial(i));
}
return 0;
}unsigned long 型のサイズが 8 バイトの環境であれば、おそらく n が 20 までは正しく n! の値を求めて表示することができるはずです。
まとめ
このページでは、C言語での「階乗の求め方」について解説しました！
階乗は、for ループや再帰関数で求めることが可能です（説明していませんが、もちろん while ループでも階乗を求めることが可能です）。
特に、この階乗を求める問題は再帰処理（再帰呼び出し）や再帰関数の説明時にもよく用いられる例であり、再帰のイメージが掴みやすい問題だと思います。for ループでも簡単に階乗は求められますが、是非再帰関数を利用した階乗の計算にも挑戦してみてください！
また、階乗は n の増加に伴って一気に値が大きくなりますので、オーバーフローに注意が必要です。特にC言語の場合は型を指定する必要があり、指定する型によって階乗が計算できる n の値も変わります。どの値の階乗まで計算する必要があるかをしっかり考え、変数や関数の返却値の型を選択するようにしましょう！
オススメの参考書（PR）
C言語学習中だけど分からないことが多くて挫折しそう...という方には、下記の「スッキリわかるC言語入門」がオススメです！
まず学習を進める上で、参考書は２冊持っておくことをオススメします。この理由は下記の２つです。
- 参考書によって、解説の仕方は異なる
- 読み手によって、理解しやすい解説の仕方は異なる
ある人の説明聞いても理解できなかったけど、他の人からちょっと違った観点での説明を聞いて「あー、そういうことね！」って簡単に理解できた経験をお持ちの方も多いのではないでしょうか？
それと同じで、１冊の参考書を読んで理解できない事も、他の参考書とは異なる内容の解説を読むことで理解できる可能性があります。
なので、参考書は２冊持っておいた方が学習時に挫折しにくいというのが私の考えです。
特に上記の「スッキリわかるC言語入門」は、他の参考書とは違った切り口での解説が豊富で、他の参考書で理解できなかった内容に対して違った観点での解説を読むことができ、オススメです。題名の通り「なぜそうなるのか？」がスッキリ理解できるような解説内容にもなっており、C言語入門書としてもかなり分かりやすい参考書だと思います。
もちろんネット等でも色んな観点からの解説を読むことが出来ますので、分からない点は別の人・別の参考書の解説を読んで解決していきましょう！もちろん私のサイトも参考にしていただけると嬉しいです！
入門用のオススメ参考書は下記ページでも紹介していますので、こちらも是非参考にしていただければと思います。
https://daeudaeu.com/c_reference_book/
