피보나치 수열

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;
int Fibonacci(int num) {
	
	if (num == 0) return 0;
	else if (num == 1)return 1;
	else return (Fibonacci(num - 1) + Fibonacci(num - 2));
}
int SIZE = 30;
void main() {
	// IO 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	clock_t start, finish;
	double duration;
	start = clock();
	Fibonacci(SIZE);
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << duration << "초" << endl;
}

c++ 를 이용해 재귀함수 형태의 피보나치 수열을 짜보았다. 

재귀함수 형태라 시간복잡도는 O(2^n)이다.