【アルゴリズム】階乗をjavascriptで実装する

2019年2月12日 09:09

階乗って何？

5! = 5 x 4 x 3 x 2 x 1 = 120

1 から n までの連続する n 個の整数の積を n を階乗って言うんです。上の例だとnが5ですね。整数の後の「!」で表現します。

なんで階乗って言うかと、階段を降りるようなに「-1」づづ減っているからです。こう考えると分かりやすいですね。

再帰版

//階乗
function factorial(num) {
 if (num < 2) return 1;
 return num * factorial(num - 1);
}

O(n)

再帰は、必ず終了条件を設定してください。でないと∞になります。値が変化する処理も必須ですね。(num - 1)

var fac = 1;
for (var i = 1; i <= 5; i++) {
 fac = fac * i;
}

O(n)

ちなみに、0!階乗は？って疑問に思うかもしれませんが、これは1です。

4! = 4 * 3 * 2 * 1 = 24 / 4 　
3! = 3 * 2 * 1 = 6 / 3
2! = 2 * 1 = 2 / 2
1! = 1 = 1 / 1
0! =1

答えをnで割っていくとパターンが見えてきます。「n の階乗は、n が 1 つ減るごとに割る数も 1 つずつ減っていく」というパターンに注目すると、「0 の階乗は 1 の階乗を 1 で割った値なので 1 」と考えられます。