フィボナッチ数列はループで書くより再帰で書いた方が書きやすい。ループではプログラマーが意識して変数を3つほど宣言する必要があるが、再帰で書けば変数は要らない。ただ、再帰には以下のような極めて致命的な問題がある。
特に後者は強烈だ。64bit符号なし整数でオーバーフローしない最大のフィボナッチ数は93項目だが、再帰でこれを求める間に令和が終わる。ループで書いた場合の計算量はO(n)なので93項目を求めている間に瞬きすらできない。
// 再帰でFibonacci数列を計算する。 uintmax_t fibonacci_recursion(uintmax_t n) { return n < 2 ? n : fibonacci_recursion(n-2) + fibonacci_recursion(n-1); } // 反復文でFibonacci数列を計算する。 uintmax_t fibonacci_loop(uintmax_t n) { if (n <= 1) return n; uintmax_t last = 1; uintmax_t sum = 1; for (uintmax_t i = 2; i < n; ++i) { auto buf = sum; sum += last; last = buf; } return sum; }
実際のソースコードを見てもループで書いたフィボナッチ関数は長ったらしい。やはり再帰で書く以外に道はない。
ここから速い再帰の話
再帰で書いた時計算量が爆発する原因は一度計算した値を覚えておらず、何度も計算してしまうからだ。それさえなくなれば再帰でもO(n)に収まる。では一度計算した値を関数内で覚えておこう。このような手法をメモ化再帰という。
普通の実装
uintmax_t memo_recursion(unsigned n) { // 一度計算した値を覚えておくための変数。すべての要素を0で初期化しておく。 static std::vector<uintmax_t> memo(94, 0); // もしnを計算したことがあればメモの内容を返す。 if(memo.at(n)) return memo.at(n); // 計算したことがなければメモに計算し、メモに代入し、値を返す。 return memo.at(n) = (n < 2 ? n: memo_recursion(n - 1) + memo_recursion(n - 2)); }
ラムダ式
せっかくC++を書いているのでC++に特有の言語機能を使って再帰を手軽に書きたい。そういえばC++11でラムダ式というのが追加されているのを思い出したのでせっかくだからラムダ式で再帰してみよう。
using memo_t = std::vector<uintmax_t>; auto f = [impl = [memo = std::make_unique<memo_t>(94, 0)](auto& fn, unsigned n) ->uintmax_t { if(memo->at(n)) return memo->at(n); return memo->at(n) = (n < 2 ? n : fn(fn, n-2) + fn(fn, n-1)); }] (unsigned n){return impl(impl, n);};
コンパイル時
テンプレートがあればもはや実行時に計算することは何もない (レポートにも書いた)。さあ、Let's template!!!!!
// コンパイル時オーバーフロー検出和算 template<class Int, Int M, Int N> struct add : std::integral_constant<Int, M + N> { static_assert(std::numeric_limits<Int>::max() - M >= N, "overflow check failed"); }; template<uintmax_t N> struct fibonacci_meta : std::integral_constant < uintmax_t, add<uintmax_t, fibonacci_meta<N - 1>::value, fibonacci_meta<N - 2>::value>::value > {}; template<> struct fibonacci_meta<0> : std::integral_constant<uintmax_t, 0> {}; template<> struct fibonacci_meta<1> : std::integral_constant<uintmax_t, 1> {}; template<uintmax_t N> inline constexpr auto fibonacci_v = fibonacci_meta<N>::value;
