与えられた数値までのすべての数値を合計する
重要性: 5
数値の合計 1 + 2 + ... + n
を計算する関数 sumTo(n)
を書いてください。
例:
sumTo
(
1
)
=
1
sumTo
(
2
)
=
2
+
1
=
3
sumTo
(
3
)
=
3
+
2
+
1
=
6
sumTo
(
4
)
=
4
+
3
+
2
+
1
=
10
...
sumTo
(
100
)
=
100
+
99
+
...
+
2
+
1
=
5050
解答のバリアントを3つ作ってください:
- for ループを使ってください。
- 再帰を使ってください。
n > 1
に対してsumTo(n) = n + sumTo(n-1)
となるような。 - 等差数列 の式を使ってください。
結果の例です:
function
sumTo
(
n
)
{
/*... your code ... */
}
alert
(
sumTo
(
100
)
)
;
// 5050
P.S. どの解決策が最も速いでしょう?そして遅いものはどれ?なぜでしょう?
P.P.S. 再帰を使って sumTo(100000)
を数えることはできますか?
ループを使った解決策です:
function
sumTo
(
n
)
{
let
sum =
0
;
for
(
let
i =
1
;
i <=
n;
i++
)
{
sum +=
i;
}
return
sum;
}
alert
(
sumTo
(
100
)
)
;
再帰を使った解決策です:
function
sumTo
(
n
)
{
if
(
n ==
1
)
return
1
;
return
n +
sumTo
(
n -
1
)
;
}
alert
(
sumTo
(
100
)
)
;
公式: sumTo(n) = n*(n+1)/2
を使った解決策です:
function
sumTo
(
n
)
{
return
n *
(
n +
1
)
/
2
;
}
alert
(
sumTo
(
100
)
)
;
P.S. 当然のことながら、この式は最速の解法です。任意の数 n に対して3つの演算しか使用しません。数学は助けます!
ループのバリアントは速度の点では2番目です。再帰とループのバリアント共に同じ数を合計していますが、再帰にはネストされた呼び出しと実行スタック管理が含まれます。それもまたリソースを取るため、より遅くなります。
P.P.S この規格は、「テールコール(末尾呼び出し)」最適化について説明しています。もし再帰呼び出しが関数の中の最後のものである場合(上の sumTo
のように)、外部の関数は実行を再開する必要はなく、その実行コンテキストを覚えておく必要はありません。その場合であれば、sumTo(100000)
はカウント可能です。しかし、もしあなたのJavaScriptエンジンがそれをサポートしていない場合は最大スタックサイズを超えたというエラーが発生します。これは、通常、スタックサイズの合計に制限があるためです。