【競プロ】漸化式と再帰関数

🕒 2019/10/29 🔄 2023/05/01

ここでは、漸化式を利用して再帰関数を作ってみます。競プロ記事の一覧はこちら。

📘 目次

漸化式

次のようにして文字列を作っていくことを考えてみます。まず、第1弾は、A だけの文字列です。第2弾は、第1弾の文字を2つ持ってきて、間にBを入れてつなげます。つまり、第2弾の文字列は A+B+A とくっつけて ABA になります。第3弾は、第2弾の文字列を2つ持ってきて、間にBを入れてつなげます。第3弾の文字列は、 ABA+B+ABA とくっつけて ABABABA になります。

このようにして、前の文字列を2つ使って、間に B を入れてつなげていく、というのを繰り返していきます。こうしたとき、第10弾や第20弾の文字列の長さを求めるにはどうすればいいでしょうか。

上のように具体的に書いて直接数えれば、第1弾の文字列の長さは1で、第2弾は3、第3弾は7となります。このまま文字列を書いて、その長さを数えていくこともできるのですが、文字列は急速に長くなっていきます。そのため、書き出して文字数を数える方法は非現実的です。

文字列の長さだけを考えればいいので、長さだけに注目してみましょう。そうすると、前の文字列を2つ使って間に文字を1つ入れるのだから、前の文字列の長さを2倍して1を足したものが次の文字列の長さになることがわかります。こうすると、プログラムで順番に計算させれば、答えが得られることがわかります。

この関係式を式で表してみましょう。第 $n$ 弾の文字列の長さを $a_n$ で表すことにします。例えば、 $a_1=1$, $a_2=3$, $a_3=7$ となります。これを用いて、「前の文字列の長さを2倍して1を足したものが次の文字列の長さになる」ことを表せば、次のようになります。
\begin{eqnarray} a_2 &=& 2a_1+1 \\[5pt] a_3 &=& 2a_2+1 \\[5pt] a_4 &=& 2a_3+1 \\[5pt] \end{eqnarray}

この式を一般的に表せば、次のようになります。\[ a_n=2a_{n-1}+1 \]先ほど見た3つの式は、この式で $n=2,3,4$ とおいたことに対応しています。

この $a_n=2a_{n-1}+1$ という式があれば、 $a_1=1$ であることも利用して、 $n=2,3,4,\cdots$ の場合を次々と求めることができます。このように、以前の情報を使って次々と先の情報を決めていくことができる式を、漸化式(ぜんかしき、recurrence relation) といいます。これを利用すれば、10番目や20番目の文字列の長さは次のように求めることができます。

#include <iostream>
using namespace std;

int main() {
  int n; cin >> n;
  int a = 1;
  for (int i = 1; i < n; i++) {
    a = 2 * a + 1;
  }
  cout << a;
  return 0;
}

1, 2, 3 を代入すると、1, 3, 7 となり、冒頭で見た結果と同じになります。また、10 や 20 を代入してみると、数字がすごく大きくなることがわかるでしょう。文字列を具体的に書いていくことは難しかったことがわかります。

漸化式と再帰関数

さて、先ほどの内容を、再帰関数を用いて書き直してみましょう。

実は、漸化式と再帰関数はすごく相性がいいのです。もともと、知りたかったのは、第 $n$ 弾目の文字列の長さです。この文字列を作るためには、第 $n-1$ 弾目の文字列を2つ持ってきて、間に B を入れてつなげればいいのでした。なので、第 $n$ 弾目の文字列の長さは、第 $n-1$ 弾目の文字列の長さを2倍して1を足せば求められます。

ある文字列の長さを求めるために、同じルールで作られる別の文字列の長さを使う、この部分が再帰的だと考えられるわけです。

これを踏まえて、文字列の長さを返す calcLength を書くと、次のようになります。

int calcLength(int n) {
  if (n == 1) return 1;
  return 2 * calcLength(n - 1) + 1;
}

三項演算子を使えば、もっとシンプルに次のように書けます。

int calcLength(int n) {
  return (n == 1)? 1: 2 * calcLength(n - 1) + 1;
}

事前にこのように定義しておけば、次のようにして計算結果が得られます。

int main() {
  int n; cin >> n;
  cout << calcLength(n);
  return 0;
}

10 や 20 を代入してみると、先ほどと同じ結果が得られることがわかるでしょう。

このように、漸化式を再帰関数で表すことで、第 $n$ 番目の値を求めることができます。

一般項

先ほどのコードに、いろいろな値を入力してみましょう。n = 5 とすれば 31 が、n = 10 とすれば 1023 が返ってきます。これらの値から気付く人がいるかもしれませんが、実は再帰関数を使わなくても $n$ 番目の文字列の長さは簡単に求めることができます。

出来上がる文字列を順番に書き出してみると、A、ABA、ABABABA、ABABABABABABABA、… となります。A と B が交互に繰り返されているように見えますね。これらの最後にBを付け加えてみましょう。そうすると、前の文字列が2回出てくることがわかります。間にBを入れて新しい文字列を作ったのだから、よく考えれば当たり前です。

文字列の長さで考えれば、前の文字列の長さに1を足して2倍すれば、次の文字列の長さに1を足したものになる、つまり、次の式が成り立つことがわかります。\[ a_n + 1 = 2(a_{n-1} + 1) \]これは、先ほどの漸化式を変形しても得られます。

このことから、もとの文字列の長さに1を足した数は、2倍ずつされていくことがわかります。第1弾の文字列の長さに1を足せば2となり、第2弾の文字列の長さに1を足せば4となり、第3弾の文字列の長さに1を足せば8となる、ということで、実は $n$ 番目の文字列の長さに1を足したものは $2^n$ と表すことができます。なので、\[ a_n=2^n-1 \]となります。計算してみると、上のコードを実行した結果とマッチすることがわかるでしょう（本当はもう少し厳密な証明が必要です）。

漸化式では、順番に値が判明していくため、例えば1000番目を計算するには手前の999番目までをすべて求める必要があります。一方、この $a_n=2^n-1$ という式では、手前がどうなっているかわからなくても、 $n$ 番目の値を直接求められるようになります。このような式を、一般項 といいます（正確には、数列の一般項です）。

高校の数列という分野では、漸化式から一般項を求める方法を学びます。競プロでは、漸化式から一般項を求められなくても、コンピュータが繰り返し計算してくれるので困ることは少ないですが、問題を考察するときには役立つこともあります。