[C++] 피보나치 수열 - 순환vs반복

순환적인 피보나치 수열 프로그램

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

 

순환함수를 이용해서 단순하고 이해하기 쉽게 피보나치 수열을 계산하는 함수이다. 

하지만 이 함수는 순환호출이 깊어질수록 비효율적이다. 

이유는 중간에 계산되었던 값을 기억하지 못하고 다시 계산하기 때문이다. n이 작을 때는 중복 계산이 비교적 작지만  n 이 커지게 되면 엄청난 순환호출이 필요하게 된다. 

 

반복적인 피보나치 수열 프로그램

int fibIter(int n) {
	if (n < 2) return n;
    else {
    	int tmp, curr = 1, last = 0;
        for (int i = 2; i <= n; i++){
        tmp = curr;
        curr += last;
        last = tmp; 
        }
        return curr;

위와 같이 반복 구조를 이용하여 비보나치 수열 계산 함수를 구현하면 더 효율적으로 계산할 수 있다. 

 

[파이썬]프로젝트 오일러 #2 (tistory.com)

[파이썬]프로젝트 오일러 #2

※피보나치 수열은 정의 자체가 순환적으로 되어있기 때문에 구현 할 때에 순환함수를 사용해서 구현하는 것이 일반적이지만 n이 커질수록 순환호출을 사용하는 방법이 무리가 될 수 있다.