[ALGORITHM] 11. 피보나치 수열 구하기

피보나치 수열은 이전 두 항을 더해서 다음 항을 만들어 내는 규칙에 따라 생성되는 수열이다.

재귀함수와 반복문을 사용해 각각 구현했다.

 

 

재귀함수

 

unsigned long long fibonacci(int n) {

	return (n <= 1) ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

 

 

반복문

 

unsigned long long fibonacci(int n) {

    if (n <= 1) {
    
        return n;
    }
    
    unsigned long long fib_n_minus_2 = 0;
    unsigned long long fib_n_minus_1 = 1;
    unsigned long long fib_n = 0;

    for (int i = 2; i <= n; ++i) {
    
        fib_n = fib_n_minus_1 + fib_n_minus_2;
        fib_n_minus_2 = fib_n_minus_1;
        fib_n_minus_1 = fib_n;
    }

    return fib_n;
}