피보나치 수(Fibonacci Numbers)의 정의는 다음과 같다.

• 0, 1로 시작
• 다음 수는 앞의 두 수의 합이 됨

규칙에 따라 수를 나열해보면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...와 같은 수열이 되는데 이를 피보나치 수열이라고 한다.

 

피보나치 수를 구하는 알고리즘을 재귀함수와 반복문으로 구현해보겠다.

 

재귀함수

function fibonacci(n) {
    if (n === 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    }
    return fibonacci(n - 2) + fibonacci(n - 1);
};

fibonacci라는 함수를 선언하였다.

인자로 n이라는 정수를 받을 것이고 n은 몇번째 피보나치 수를 구할 것인지를 의미한다.

 

2~6라인: 피보나치수의 첫번째 수와 두번째 수는 각각 0과 1로 시작한다는 것이 규칙이었기 때문에 n이 0일때 0을 리턴, n이 1일때 1을 리턴한다.

 

7라인: 피보나치의 n번째 수의 정의는 앞의 두 수의 합이다. 즉, n-2번째 수와 n-1번째 수의 합을 의미한다.

여기서 n-2번째 수와 n-1번째 수를 잘 생각해보면, n-2번째 수는 n-4번째 수와 n-3번쨰 수의 합을 의미하고, n-1번째 수는 n-3번째 수와 n-2번째 수의 합을 의미한다. 그렇기 때문에 fibonacci(n - 2)와 fibonacci(n-1)의 합을 return하면 n번째 피보나치 수를 return한다.

 

반복문

function fibonacci(n) {
    let n1 = 0;
    let n2 = 1;
    let result = 0;

    for (let i = 0; i < n - 1; i ++) {
        result = n1 + n2;
        n1 = n2;
        n2 = result;
    }
    return result;
}

반복문으로 구현한 fibonacci 함수이다.

재귀함수와 마찬가지로 몇번째 피보나치 수를 구할것인지를 의미하는 n을 인자로 받는다.

 

2~3라인 : 첫번째 수와 두번째 수는 0과 1로 선언한다.

4라인: n-1, n-2번째 수를 더한 값을 저장할 변수

6~10라인: n번째 피보나치 수를 구할 때 까지 반복하는 루프. 매 루프마다 n1과 n1을 더해서 result에 담고 n1을 n2로 n2를 result로 할당한다.

11라인: n번째 피보나치 수를 return한다.