#include "..\CookHeader.h"

int count_dp = 0, count_recu = 0;

int recu_fibo(int n) {
	count_recu++;
	if (n < 2)
		return 1;
	else
		return recu_fibo(n - 1) + recu_fibo(n - 2);
}

int dp_fibo(int n) {
	Array <int> memo = { 1, 1 };
	if (n < 2)
		return memo[n];
	else {
		for (int i = 2; i < n + 1; i++) {
			memo.push_back(memo[i - 1] + memo[i - 2]);
			count_dp++;
		}
		return memo[n];
	}
}

int main() {
	println("## 30번째 피보나치 수열 ##");

	int res;
	res = recu_fibo(30);
	println("재귀 방식 ---> 답: " + to_string(res) + ", 반복수 : " + to_string(count_recu));

	res = dp_fibo(30);
	println("DP 방식 ---> 답: " + to_string(res) + ", 반복수 : " + to_string(count_dp));
}