반복-피보나치 수열 계산

피보나치 수열

- 앞의 두 숫자를 더해 뒤의 숫자를 만듦

- 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

 

순환 호출을 사용하여 구현

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

- 순환 호출이 진행될수록 계산 횟수 증가

- 복잡도 T(n)=T(n-1)+T(n-2)+C

- 시간 복잡도 O(2^n)

 

반복을 이용하여 구현

int fib_iter(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;

	int pp = 0;
	int p = 1;
	int result = 0;

	for (int i = 0; i <= n; i++) {
		result = p + pp;
		pp = p;
		p = result;
	}
	return result;
}

- result=p+pp: 앞의 두 수를 더한 값이 뒤의 숫자가 됨

- pp=p: 반복이 진행되며 뒤의 숫자였던 값이 앞의 숫자가 됨