[C/C++] 피보나치 수열

n번째 피보나치 수를 구하는 재귀 함수. 직관적이나 실행시간 O(n^2)

int fib(int n)
{
    if (n <= 2)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}

void main() 
{
	for (int i = 0; i < 10; i++)
		printf("%d\n", fib(i));	
}

 

 

중복 계산이 일어나지 않도록 루프 방식으로 개선.  실행시간 O(n)

// fib(n) = fib(n-1) + fib(n-2)

int fib(int n)
{
	int f = 0, f1 = 0, f2 = 1;  // f: fib(n), f1: fib(n-1), f2: fib(n-2)

	for (int i = 1; i <= n; i++)
	{
		f = f1 + f2;
		f2 = f1;
		f1 = f;
	}
	return f;
}

void main() 
{
	for (int i = 0; i < 10; i++)
		printf("%d\n", fib(i));	
}