🕒 2019/11/07 🔄 2024/10/16

フィボナッチ数列と再帰関数（メモ化再帰）

🐠

ここでは、フィボナッチ数列を通じて、再帰関数のメモ化について見ていきます。

📘 目次

フィボナッチ数列

次のように数が並んでいるとします。\[ 0,1,1,2,3,5,8,13,21,\cdots \]1つ前と2つ前の数を足して新しい数を計算する、というルールです。例えば、 $21$ の次は、 $13+21=34$ になる、ということです。

初めの2つの数 $0,1$ を決めれば、その後の数は、次々と確定していきます。このようにして決まる数の列を、フィボナッチ数列(Fibonacci sequence) といいます。フィボナッチ数列は、競プロをはじめ、様々な分野で出てきます。

ここでは、フィボナッチ数列の $n$ 番目の数を求める fibonacci(n) という関数を、再帰関数で書くことを考えましょう。なお、先頭の $0$ を $0$ 番目とします。つまり、fibonacci(0) = 0, fibonacci(1) = 1 ということです。

1つ前の数と2つ前の数を足せば次の数が出てくることから、次のように計算すればいいことがわかるでしょう。

fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2);

こうして、次のようなコードで求められることがわかります。

#include <iostream>
using namespace std;

long long fibonacci(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

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

n に 10 くらいまでの値を入力すれば、手で計算したときと同じ結果が得られることがわかるでしょう。

今まで見た和や階乗と再帰関数などでの再帰とは違って、 $n-1$ と $n-2$ の2つの結果を使っている点が異なっています。

メモ化再帰

さて、ここで、先ほどのコードを実行して、40 を入力してみましょう。また、入力する値を1ずつ増やしていくと、あるところからもっさりとした動きになることがわかります。

実は、このコードでは、計算量がすごいことになっています。関数が何回呼び出されたかを表示するために次のようにコードを書き換えてみてみます。

#include <iostream>
using namespace std;

int cnt = 0;
int fibonacci(int n) {
  cnt++;
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
  int n; cin >> n;
  cout << fibonacci(n);
  cout << "\\n" << cnt;
  return 0;
}

40 を入力すると、3億回程度も呼び出されていることがわかります。40番目の値を計算するだけなのに、どうしてこんなことになるのでしょうか。

先ほど、「今まで見た再帰とは、 $n-1$ と $n-2$ の2つの結果を使っている点が異なっている」と書きましたが、この点が原因です。このせいで同じような計算を何度もしていることになります。これを理解するには、どのように関数が呼び出されているかを見てみるのがいいでしょう。

5を入力した場合を考えましょう。すると、4番目と3番目の和を返そうとします。4番目は、3番目と2番目の和、3番目は2番目と1番目の和、というようにどんどんさかのぼっていきます。こうして4番目が計算できたら、今度は3番目を同じように計算し、その和が5番目の数になる、という流れです。 $n$ 番目の値を $F_n$ で表すことにすると、次のような計算をしていることになります。

\begin{eqnarray}
& &
F_5 \\[5pt]
&=&
F_4 + F_3 \\[5pt]
&=&
(F_3+F_2) + (F_2+F_1) \\[5pt]
&=&
\{(F_2+F_1)+(F_1+F_0)\} + \{(F_1 + F_0)+F_1\} \\[5pt]
&=&
[\{(F_1+F_0)+F_1\}+(F_1+F_0)] + \{(F_1 + F_0)+F_1\} \\[5pt]
\end{eqnarray}

しかし、よく考えてみると、例えば、2番目の項 $F_2$ を何度も $F_1+F_0$ に分解して計算するのは無駄です。一度値がわかってしまえば、今後はその値を使えばよく、再帰させる意味はありません。これをやっていなかったために、呼び出し回数がすごいことになっていたのです。

そのため、 $n$ 番目の数字を格納する配列を使うように変えてみます。

#include <iostream>
#include <vector>
using namespace std;
vector<long long> memo(50, -1);

int cnt = 0;
long long fibonacci(int n) {
  cnt++;
  if (memo[n] != -1) return memo[n];
  return memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
  int n; cin >> n;
  memo[0] = 0;
  memo[1] = 1;
  cout << fibonacci(n);
  cout << "\\n" << cnt;
  return 0;
}

初めに配列を -1 で初期化し、0番目と1番目の値を設定します。漸化式を使ってどんどん計算はしていきますが、計算したものは配列 memo に格納し、計算済みなら再利用するようにしています。

これにより、計算回数は激減します。実際、上のコードを実行してみると、40 を代入すれば 79 回となります。

このように、途中の計算結果を配列に格納しておいて、必要ならそれを使いまわす、というテクニックを競プロではよく使います。このようなテクニックを、メモ化(memoization) といい、メモ化を使った再帰をメモ化再帰といいます。これにより無駄な再帰処理の回数が減り、計算結果・計算時間が大幅に減ります。

ボトムアップでフィボナッチ数列を求める

先ほどは、フィボナッチ数列の $n$ 番目の値を求めるのに、 $n$ 番目からさかのぼって値を求めていくことで計算しました。その際、一度さかのぼって判明した値は、その後の計算で使いまわすことで計算量が減らせることを見ました。

これを見て、「そもそも前から順番に求めていけば楽じゃね？」と思う人もいるでしょう。実際、フィボナッチ数列の $n$ 番目の値を求めるには、前から求めていく方が速くて、しかも、わかりやすいです。

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n; cin >> n;
  vector<long long> fibonacci(50);

  fibonacci[0] = 0;
  fibonacci[1] = 1;
  for(int i = 2; i <= n; i++) {
    fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
  }
  cout << fibonacci[n];
  return 0;
}

今の場合は、漸化式が与えられているので、このように書くほうが自然に感じられるでしょう。しかし、問題によっては、手前にさかのぼっていくコードは思いつきやすいけど、前から順番に求めていくコードは思いつきにくい、というものもあります。そのため、どちらの考え方もマスターしておく方がいいでしょう。

一般に、(1) 問題を小さく分解して大きな問題を解くこと、(2) 途中で計算した結果を記録して同じ計算をしないようにすること、この2つを満たす手法を、動的計画法(dynamic programming, DP) といいます。トップダウンで計算したときに使ったメモ化再帰も、ここで見たボトムアップでの計算も、動的計画法の一種です。動的計画法は、競プロではいろんな形で出題されます。

慣れていないと少し難しいですが、AtCoder EDPC A - Frog 1 してみましょう。メモ化再帰を使った解答例は、提出 #8244340 にあります。また、フィボナッチ数列に似たリュカ数を計算する問題 AtCoder ABC 079 B - Lucas Number も練習になるでしょう。

おわりに

ここでは、フィボナッチ数列の n 番目の数を求めるために、再帰関数を使う方法を見ました。また、そのときに、途中の計算結果を配列に格納して使いまわすことで速く計算する、メモ化再帰についても見てきました。計算時間が重要な競プロではよく使うテクニックです。