【アルゴリズム】階乗をjavascriptで実装する
階乗って何?
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です。
答えをnで割っていくとパターンが見えてきます。「n の階乗は、n が 1 つ減るごとに割る数も 1 つずつ減っていく」というパターンに注目すると、「0 の階乗は 1 の階乗を 1 で割った値なので 1 」と考えられます。
この記事が気に入ったらサポートをしてみませんか?