처음 프로그래밍을 배울 때, 특히 재귀함수를 다룰 때 팩토리얼 다음으로 자주 등장하는 예제는 피보나치 수열이다.
1 2 3 4 | int fibonacci(int n) { if (n == 0 || n == 1) return 1; return fibonacci(n-1) + fibonacci(n-2);} |
이렇게 하면 n이 커질 때 너무 오래 걸리기 때문에 배열을 사용해서 계산하는 법이 이어서 등장하기도 한다.
1 2 3 4 5 6 7 8 9 | 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];} |
이런 방식을 다이나믹 프로그래밍이라고 하는데, 아래처럼 하면 메모리 사용량을 조금 아낄 수 있다.
1 2 3 4 5 6 7 8 9 | 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로 시작하는 피보나치 수열을 구하는 좀 더 일반적인 함수는 다음과 같이 만들 수 있다.
1 2 3 4 5 6 7 8 9 | 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을 쓰고 싶은 사용자가 있으면 쓸 수 있도록 템플릿으로 만들어 줄 수도 있다.
1 2 3 4 5 6 7 8 9 10 | 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;} |
한편 템플릿 기능을 활용하면 다음처럼 색다른 방식으로 피보나치 수열을 구할 수 있다. 이런 방식을 템플릿 메타프로그래밍이라고 한다. 이 방식의 장점은 계산이 컴파일하면서 일어나기 때문에 실행할 땐 아무런 피보나치 계산도 일어나지 않는다는 점이다. 사실 이런 방식으로 컴퓨터의 모든 연산을 수행하는 것이 가능하다!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #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 이라는 클래스가 각각 수식, 숫자, 덧셈의 역할을 수행한다. 이렇게 하면 각 연산이 일어날 때에 뭔가 부가적인 일(자동으로 미분을 시켜준다던가...)을 하는 것이 가능하다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #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;} |
