再帰テンプレート

C++

今年の仕事始めの日に、「午前中いっぱい(3H)で、何かプログラム書け」というイベントがあったのですが、その時に使ったネタを書いておきます。

数列の計算

単純な数列として、0..nまでの和、nの階乗、フィボナッチ数列などがありますが、例えば、0..nまでの和を求める関数は、以下のように書けると思います。

int sum(const int x)
{
	if (x == 0) { return 0; }
	return x + sum( x - 1 );
}

実際に数列を使う場合には、以下のようにするかと思います。

	int x;
	  ...
	std::cout << "sum(x) = " << sum(x) << "\n";
	  ...
	std::cout << "sum(400) = " << sum(400) << "\n";

ここで、sum(400)は明らかに定数ですので、実行時に毎回算出するのは無駄だと言えます。
しかしながら、sum(400)の計算結果を定数として定義するというのもあまり良いとは思えません。
そこで、テンプレートを使ってコンパイル時に計算させるという方法があります。

///////////////////////////////////////////////////////////////////////////////
// 0..nの合計を求める

// n番目を返す
template<int x> struct Sum
{
	enum
	{
		value = x + Sum<x - 1>::value
	};
};

// xが0の時は0を返す
template<> struct Sum<0>
{
	enum
	{
		value = 0
	};
};

n番目を返すテンプレートは、enumのvalueを(1回だけ代入できる)変数のように利用して、再帰的に定義されます。そして、そのままでは無限ループになってしまうので、0番目だけは、別途定義して、0を設定します。
実際に使う場合は、以下のようになります。

	std::cout << "Sum(400) = " << Sum<400>::value << "\n";

これで、0..nまでの和をコンパイル時に計算し、実行時間を短縮(微々たるものですが)できます。
しかしながら、あまり大きな値を与えてしまうと、コンパイラがテンプレートを処理する際の限界値に達してしまうことがあります。
例えば、自分の環境(VS2008)では、

	std::cout << "Sum(489) = " << Sum<489>::value << "\n";

これは計算可能でしたが、

	std::cout << "Sum(490) = " << Sum<490>::value << "\n";

これはコンパイラが落ちてしまいました。

最後に、実際にイベントで発表したソースを以下に記しておきます。
＃ 明らかな間違いやコメントは修正しています。

///////////////////////////////////////////////////////////////////////////////
// 0..nの合計を求める

// n番目を返す
template<int x> struct Sum
{
	enum
	{
		value = x + Sum<x - 1>::value
	};
};

// 0番目を返す
template<> struct Sum<0>
{
	enum
	{
		value = 0
	};
};

///////////////////////////////////////////////////////////////////////////////
// n!を求める

// n番目を返す
template<int x> struct Factorial
{
	enum
	{
		value = x * Factorial<x - 1>::value
	};
};

// 0番目を返す
template<> struct Factorial<0>
{
	enum
	{
		value = 1
	};
};

///////////////////////////////////////////////////////////////////////////////
// 0..nのフィボナッチ数列を求める

// n番目を返す
template<int x> struct FibonacciNumber
{
	enum
	{
		value = FibonacciNumber<x - 2>::value + FibonacciNumber<x - 1>::value
	};
};

// 1番目を返す
template<> struct FibonacciNumber<1>
{
	enum
	{
		value = 1
	};
};

// 0番目を返す
template<> struct FibonacciNumber<0>
{
	enum
	{
		value = 0
	};
};

///////////////////////////////////////////////////////////////////////////////

↑ヘッダファイル

#include <iostream>
#include "FibonacciNumber.hpp"

int sum(const int x)
{
	if (x == 0) { return 0; }
	return x + sum( x - 1 );
}

int main(int argc, char* argv[])
{
	std::cout << "Sum(489) = " << Sum<489>::value << "\n";
	// Sum(490)でコンパイラがギブアップ

	std::cout << "sum(500) = " << sum(500) << "\n";

	std::cout << "Fibonacci(46) = " << FibonacciNumber<46>::value << "\n";
	// Fibonacci(47)でオーバーフロー

	std::cout << "Factorial(12) = " << Factorial<12>::value << "\n";
	// Factorial(13)でオーバーフロー

	getchar();
}

↑ソースファイル