Recursive_Fibonacci Sequence

Explain

• 피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞 두 피보나치 수의 합이된다. (\( F_n = F_{n-1} + F_{n-2} \))
• 모든 문제를 Recursion 한 방식으로 생각하는 것뿐만 아니라 그 이후 반드시 다른방식(Iteration, Memozation) 등 과 비교하여 최적의 방법을 찾아내는 작업도 병행되어야 하는 점을 알아야 된다.
• 이 문제는 Recursion 방식의 큰 위험성에 대해 파악할 수 있는 문제이다.

Formula

$$\begin{equation*} F_n=F_{n-1}+F_{n-2}, \quad F_1=1, \quad F_2=1 \end{equation*}$$ 

$$\begin{equation*} 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, \ldots \end{equation*}$$

Recursion

//Time complexity O(n^2)
long fibo(long n)
{
	if(n < 2)
	{
		return n;
	}
	else
	{
		return fib(n-1) + fib(n-2);
	}
}

Memozation

//allocate array for memo, setting all entries to zero;
//initialize memo[1] and memo[2] to 1;
//Time complexity O(n)
long fibo(long n)
{
	if(memo[n] == 0)
	{
		memo[n] = fib(n-1) + fib(n-2);
	}

	return memo[n];
}

Time Complexity

• 위처럼 Recursion, Memozation의 차이는 각 \( O(n^2) , O(n) \) 으로 인자의 크기가 커질수록 연산 속도의 차이는 매우 증가한다는 것을 알 수 있다. 
• Memozation 방식의 경우 메모리에 계산된 수를 저장해두는 방식이라 Iteration 방식과 달리 연산의 중복이 없으므로 훨씬 효율적인 속도가 나오는 것을 알 수 있다.

Reference.

• Wiki - 피보나치 수열
• Wiki - 피보나치 수 프로그램
• Wiki - Memozation