フィボナッチ数を求めるプログラム

C++版。g++ 4.0.1でコンパイル。

再帰

#include <iostream>
using namespace std;

template<int N>
struct fib
{
  enum { Value = fib<N-2>::Value + fib<N-1>::Value };
};

template<>
struct fib<1>
{
  enum { Value = 1 };
};
template<>
struct fib<0>
{
  enum { Value = 0 };
};

int main()
{
  cout << fib<50>::Value << endl;
  return 0;
}

反復?

#include <iostream>
using namespace std;

template<long long a, long long b, int N>
struct fib_iter
{
  enum { Value = fib_iter<a+b, a, N-1>::Value };
};
template<long long a, long long b>
struct fib_iter<a, b, 0>
{
  enum { Value = b };
};
template<int N>
struct fib
{
  enum { Value = fib_iter<1, 0, N>::Value };
};

int main()
{
  cout << fib<50>::Value << endl;
  return 0;
}