🕒 2019/10/30 🔄 2024/10/16

和や階乗と再帰関数

☂

ここでは、 $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$ までの和や積を、再帰関数を用いて求める方法を見てきました。同じ構造で、より小さなステップに分解することで、再帰関数が使えるようになります。どちらの例も、再帰関数を使って書ける例でしたが、数学としても重要な内容で、今後いろいろな場面で登場することになります。