3. Fibonacci

Algorithms

What is Fibonacci?

Fibonacci 수열이란, 다음 수는 앞의 두 수의 합으로 이루어진 수열을 말한다.
규칙에 따라 수를 나열해 보면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…와 같은 수열이 된다.


[Problem]

피보나치 수는 F(0) = 0, F(1) = 1일 때, 2 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 점화식입니다.
2 이상의 n이 입력되었을 때, fibonacci 함수를 제작하여 n번째 피보나치 수를 반환해 주세요.
예를 들어 n = 3이라면 2를 반환해주면 됩니다. 즉, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…에서 3번째 피보나치의 수는 2이다.


[Algorithms]

  1. n이 0일 경우, 0을 리턴하고, 1일 경우, 1을 리턴한다.(피보나치 수열에서 0번째는 0, 1번째는 1이기 때문이다.)
  2. n이 2이상일 경우, 앞의 두 수의 합으로 계산되는 재귀 호출을 사용하여 구현한다.
  3. 함수에서 n이라는 정수를 받을 것이고, n은 몇 번째 피보나치 수를 구할 것인지를 의미한다. 예를 들어, n이 3이면, 피보나치 수열 중 3번째 피보나치 수를 구하는 함수를 구현하는 것이고, 그 값은 2이다.


[Solution]

1
2
3
4
5
6
7
8
9
10
11
12
function fibonacci(num){
  var a = 1, b = 0, temp;

  while (num >= 0){
    temp = a;
    a = a + b;
    b = temp;
    num--;
  }

  return b;
}


[Best Practice]

1
2
3
4
5
6
7
8
9
function fibonacci(num) {
  if(num === 0) {
    return 0;
  } else if(num === 1) {
    return 1;
  }

  return fibonacci(num - 1) + fibonacci(num - 2);
}