テンプレートを使って簡単な漸化式を計算する

コンパイル時に値を計算するための方法についてです。フィボナッチ数列を例にとってみましょう。
$a_{n+2}=a_{n}+a_{n+1}, n=0, 1, 2,..., \\a_0=a_1=1$
この数列の答えはこのようになります。

n	0	1	2	3	4	5	6	7	8	...
$a_n$	1	1	2	3	5	8	13	21	34	...

実際に4つほど書き下したものが下の式です。
$a_{4}=a_{3}+a_{2}$
$a_{3}=a_{2}+a_{1}$
$a_{2}=a_{1}+a_{0}$
$a_{1}=1$
$a_{0}=1$
これに対応するコードを書くと次のようになります。テンプレート引数に値を指定すると関数を生成するので、現れる関数は全て別のものです。

int a4(){
	return a3()+a2();
}
int a3(){
	return a2()+a1();
}
int a2(){
	return a1()+a0();
}
int a1(){
	return 1;
}
int a0(){
	return 1;
}

テンプレート引数を指定すると上の関数(a0,a1,a2,a3,a4)などが生成されるので、それらの関数に共通している番号Nを関数のラベルだと思って次のように考えてみます。

//注：文法的に誤り
int a<4>(){
	return a<3>()+a<2>();
}
int a<3>(){
	return a<2>()+a<1>();
}
int a<2>(){
	return a<1>()+a<0>();
}
int a<1>(){
	return 1;
}
int a<0>(){
	return 1;
}

これをNについて一般化すると下のようになります。a<1>とa<0>は1を返すだけなので特殊な場合とします。

//一般化
int a<N>(){
	return a<N-1>()+a<N-2>();
}
//特殊化
int a<1>(){
	return 1;
}
int a<0>(){
	return 1;
}

C++の書式でテンプレート化したものが以下のコードです。

//テンプレート化
template <int N>
int a(){
	return a<N-1>()+a<N-2>();
}
//特殊化
template <>
int a<1>(){
	return 1;
}
template <>
int a<0>(){
	return 1;
}

実際に計算してみたものがこちら。

int main(){
	std::cout << a<8>() << std::endl;	//34