【終了コード9】ABC079 B - Lucas Number のTLE問題（C++, 配列と再帰関数の処理速度の違い）

Atcoder公式のC++教材、AtCoder Programming Guide for beginners (APG4b)に取り組んでいるのですが、3章の最初の演習問題で躓いたので共有します。

ABC079 B問題「Lucas Number」 とは

chatGPTに聞いてみたルカ数について。
一言でまとめると、初項が2で2番目の項が1のフィボナッチ数列です。

ルカ数列は、数学の世界で見られる興味深いパターンの一つです。この数列は、2つの初期値を持ち、その後の各項は直前の2つの項の和として生成されます。
最初の2つの項が2と1であるとき、次の項はそれらの和であり、その後も同様に続きます。つまり、数列は次のように始まります：2, 1, 3, 4, 7, 11, 18, 29, 47, ..

【間違えた回答】再帰関数（C++）

最初問題を読んだ時、「お、これはPiscineでもやったアレではないか！」と再帰関数に飛びつきました。しかし実行してみると終了コード9(TLE)、、実行に時間がかかりすぎていると怒られてしまいました。

#include <iostream>
using namespace std;

int ft_lucas(int64_t N)
{
	if (N == 0)
		return 2;
	if (N == 1)
		return 1;
	return (ft_lucas(N - 1) + ft_lucas(N - 2));
}

int main(void)
{
	int64_t N;
	cin >> N;
	int64_t ans = 0;
	ans = ft_lucas(N);
	cout << ans << endl;
	return 0;
}

【正解になった回答】配列（C++）

色々調べた結果、再帰関数はループよりは早いものの、配列に1つずつ要素をメモしておく処理よりは数倍遅いことがわかりました。

理由は明確で、ft_lucas(N-1)とft_lucas(N-2)からの呼び出しで複数回おなじ関数が呼び出されるため、より大きな項の数を求める場合には重複した計算が指数関数的に増えていきます。再帰が深くなればなるほどスタックに多数のフレームが重なり、スタックオーバーヘッドが起こるリスクも高くなります。

しかし配列を使用した場合は、計算結果を都度格納していくため。重複計算を防ぐことが可能になります。再計算が不要になり、処理時間が大幅に削減されることに繋がります。

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

int main(void)
{
	int64_t N;
	cin >> N;
	vector<int64_t> lucasnum(N + 1);
	lucasnum.at(0) = 2;
	lucasnum.at(1) = 1;
	for (int i = 2; i <= N; i++)
	{
		lucasnum.at(i) = lucasnum.at(i - 1) + lucasnum.at(i - 2);
	}
	cout << lucasnum.at(N) << endl;
	return 0;
}

実際に二つのコードの実行時間の差は歴然でした、、
（下側が再帰関数によるもの、上側が配列によるもの）

まとめ

再帰関数の方がスタイリッシュに記述できるので飛びつきがちでしたが、その都度適切なアルゴリズム・データ構造を利用できるように精進したいですね。

引き続き楽しいAtcoderライフを！