【競プロ】和や階乗と再帰関数
ここでは、 $1$ から $n$ までの整数の和や積を、再帰関数を用いて書く方法を見ていきます。競プロ 記事の一覧はこちら。
整数の和
ここでは、 $1$ から 整数 $n$ までの整数の和を求めるコードを、再帰関数を用いて書いてみます。 $1$ から $n$ までの整数の和というのは、 $n=5$ なら $1+2+3+4+5$ のことで、 $n=100$ なら、 $1+2+\cdots+100$ のことです。
関数として期待する働きとしては、 $n$ を渡すと、「$1$ から $n$ までの和が返ってくる」というものでしょう。これをコードで書いてみます。
まずは $n=5$ の場合を例に考えます。 $1$ から $5$ までの和は、次のように変形できます。\[ 1+2+3+4+5=(1+2+3+4)+5 \]カッコをつけたところで、足した答えは変わりません。そのカッコの部分をよく見れば、「 $1$ から $4$ までの和」となっています。この部分は「$1$ から $n$ までの和が返ってくる」関数を再利用できることがわかります。
これを踏まえて、 $1$ から $n$ までの整数の和を返す関数 calcSum
の構造を考えてみましょう。整数 n
を受け取って、n
と calcSum(n - 1)
との和を返せばいいですね。後者は、さらに n - 1
と calcSum(n - 2)
との和を返せばいいです。こうして何度も処理を繰り返していくことで、答えが得られそうだ、と予想できます
このままではいつまでも処理が続いてしまうので、 n = 1 のときには 1 が返るようにしましょう。 n = 0 のときに 0 が返るようにしてもいいですね。どちらでもいいので、どこかで止まるための処理を加えます。これより、calcSum
は次のように書けます。
#include <iostream>
using namespace std;
int calcSum(int n) {
return (n == 1)? 1: n + calcSum(n - 1);
}
int main() {
int n; cin >> n;
cout << calcSum(n);
return 0;
}
例えば、3 を入力すると、 $1$ から $3$ までの整数の和が返ってきます。その流れを順番に追ってみましょう。
まず、3 を入力すれば、calcSum(3)
を返そうとします。この関数内の処理を見ると、3 + calcSum(2)
を返すことがわかります。後者ではまた同じ関数が呼び出されて、3 + 2 + calcSum(1)
を返すことがわかります。後者ではまた同じ関数が呼び出されますが、今回は n == 1
が TRUE
なので、3 + 2 + 1
を返すことがわかります。こうして、calcSum(3)
は、 $1$ から $3$ までの整数の和を返すことがわかります。
他の値を代入したときも同じです。正の整数を入れれば、 $1$ からその値までの整数の和が返ってくることは、同じように考えればわかるでしょう。このように、再帰関数を使うには、同じ構造を持つ「より小さなステップ」に分解することが重要となります。
漸化式と再帰関数で見た漸化式を使って書けば、この再帰関数は、次の漸化式を考えていることに対応します。\[ S_n = n + S_{n - 1} \]さらに、 $S_1 = 1$ という条件を加えると、正の整数について、 $S_n$ の値が順番に決まっていきます。
なお、 $1$ から $n$ までの整数の和は、 $\dfrac{1}{2}n(n+1)$ で求められることが知られています。 n * (n + 1) / 2
を利用して試してみましょう。なぜこの式で得られるかは、また別の機会に見ることになります(参考:【競プロ】和の公式(1からnまでの和))。
$1$ から $n$ までの整数の和を利用すると、AtCoder ABC 099 B - Stone Monumentなどが解けるでしょう。何を計算しないといけないのか、少し考える必要がありますが、トライしてみましょう。
階乗
先ほどの「和」の部分を「積」に置き換えたもの、つまり、 $1$ から整数 $n$ までの整数の積も、同じように再帰関数を使って表すことができます。なお、 $1$ から整数 $n$ までの整数の積とは、 $n=5$ なら、 $1\times 2\times 3\times 4\times 5$ のことです。
先ほどと同じように考えれば、「 $n$ までの整数の積」を計算するには、 $n$ に「 $n-1$ までの整数の積」を掛ければいいことがわかります。これを踏まえて、calcProduct
という関数を作ってみると、次のように書けるでしょう。
#include <iostream>
using namespace std;
int calcProduct(int n) {
return (n == 1)? 1: n * calcProduct(n - 1);
}
int main() {
int n; cin >> n;
cout << calcProduct(n);
return 0;
}
こうすれば、calcProduct(5)
を呼び出すと $5$ までの積が、calcProduct(n)
を呼び出すと $n$ までの積が返ってくるようになります。ただ、数字はどんどん大きくなってすぐにオーバーフローしてしまいますが。
余りの計算でも紹介した AtCoder ABC 055 B - Training Camp では、この calcProduct
を少し変形して作成することもできます。再帰関数を使った方法でも提出してみましょう。
ちなみに、数学の世界では、この $1$ から整数 $n$ までの整数の積には、階乗(factorial) という名前がついていて、 $n!$ という記号で表すことになっています。階乗は、将来、順列や組合せを考えるときにも登場します。
おわりに
ここでは、 $1$ から整数 $n$ までの和や積を、再帰関数を用いて求める方法を見てきました。同じ構造で、より小さなステップに分解することで、再帰関数が使えるようになります。どちらの例も、再帰関数を使って書ける例でしたが、数学としても重要な内容で、今後いろいろな場面で登場することになります。