사서 고생하는 피보나치 수열 구하기

처음 프로그래밍을 배울 때, 특히 재귀함수를 다룰 때 팩토리얼 다음으로 자주 등장하는 예제는 피보나치 수열이다.

int fibonacci(int n) {
    if (n == 0 || n == 1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

이렇게 하면 n이 커질 때 너무 오래 걸리기 때문에 배열을 사용해서 계산하는 법이 이어서 등장하기도 한다.

int fibonacci(int n) {
    int a[N];  // N = 관심 있는 n의 최대 크기+1
    a[0] = 1;
    a[1] = 1;
    for(int i=2; i<=n; i++) {
        a[i] = a[i-1] + a[i-2];
    }
    return a[n];
}

이런 방식을 다이나믹 프로그래밍이라고 하는데, 아래처럼 하면 메모리 사용량을 조금 아낄 수 있다.

int fibonacci(int n) {
    int a = 0, b = 1, c = 1;
    for(int i=0; i<n; i++) {
        c = a+b;
        a=b;
        b=c;
    }
    return c;
}

1, 1 대신에 다른 숫자 a, b로 시작하는 피보나치 수열을 구하는 좀 더 일반적인 함수는 다음과 같이 만들 수 있다.

int fibonacci(int a, int b, int N) {
	int c = b;
	for(int i=1; i<N; i++) {
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}

피보나치 수열은 꽤 빠르게 증가하는데 int 타입은 21억까지밖에 표현을 못한다. long이나 double을 쓰고 싶은 사용자가 있으면 쓸 수 있도록 템플릿으로 만들어 줄 수도 있다.

template <typename T>
T fibonacci(T a, T b, int N) {
	T c = b;
	for(int i=1; i<N; i++) {
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}

한편 템플릿 기능을 활용하면 다음처럼 색다른 방식으로 피보나치 수열을 구할 수 있다. 이런 방식을 템플릿 메타프로그래밍이라고 한다. 이 방식의 장점은 계산이 컴파일하면서 일어나기 때문에 실행할 땐 아무런 피보나치 계산도 일어나지 않는다는 점이다. 사실 이런 방식으로 컴퓨터의 모든 연산을 수행하는 것이 가능하다!

#include <iostream>
using namespace std;

template <int n>
struct Fibonacci { enum { value = Fibonacci<n-1>::value + Fibonacci<n-2>::value }; };

template <>
struct Fibonacci<0> { enum { value = 1 }; };

template <>
struct Fibonacci<1> { enum { value = 1 }; };

int main() {
    cout << Fibonacci<0>::value << endl;
    cout << Fibonacci<1>::value << endl;
    cout << Fibonacci<2>::value << endl;
    cout << Fibonacci<3>::value << endl;
    cout << Fibonacci<4>::value << endl;
    cout << Fibonacci<5>::value << endl;
    cout << Fibonacci<6>::value << endl;
    cout << Fibonacci<7>::value << endl;
    cout << Fibonacci<8>::value << endl;
    cout << Fibonacci<9>::value << endl;
    cout << Fibonacci<10>::value << endl;
    cout << Fibonacci<11>::value << endl;
}

CRTP라는 이상한 방식을 사용해서 조금 변태같은 방법으로 피보나치 수열을 구할 수도 있다. Expression, Integer, Sum 이라는 클래스가 각각 수식, 숫자, 덧셈의 역할을 수행한다. 이렇게 하면 각 연산이 일어날 때에 뭔가 부가적인 일(자동으로 미분을 시켜준다던가...)을 하는 것이 가능하다.

#include <iostream>
using namespace std;

template <typename T>
struct Expression {
	const T& cast() const { return static_cast<const T&>(*this); }
	int value() const { return cast().value(); }
};

struct Integer : Expression<Integer> {
	template<typename T>
	Integer& operator=(const Expression<T> &rhs) {
		N = rhs.value();
		return *this;
	}
	Integer(int N=0) : N(N) {}
	int value() const { return N; }
private:
	int N;
};

template <typename L, typename R>
struct Add : public Expression<Add<L,R> > {
	Add(const Expression<L> &lhs, const Expression<R> &rhs) : lhs(lhs.cast()), rhs(rhs.cast()) {}
	int value() const { return lhs.value() + rhs.value(); }
private:
	const L& lhs;
	const R& rhs;
};

template <typename L, typename R>
Add<L,R> operator+(const Expression<L>& lhs, const Expression<R>& rhs) {
	return Add<L,R>(lhs, rhs);
}

template <typename T>
T fibonacci(T a, T b, int N) {
	T c = b;
	for(int i=1; i<N; i++) {
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}

int main() {
	Integer a = 1, b = 1;
	for(int i=0; i<12; i++) {
		Integer f = fibonacci(a, b, i);
		cout << f.value() << "\t" << fibonacci(1, 1, i) << endl;
	}

	return 0;
}