[DAY 6] Recursion: Fibonacci Numbers

The Fibonacci Sequence

The Fibonacci sequence appears in nature all around us, in the arrangement of seeds in a sunflower and the spiral of a nautilus for example.

The Fibonacci sequence begins with fibonacci(0) = 0 and fibonacci(1) = 1 as its first and second terms. After these first two elements, each subsequent element is equal to the sum of the previous two elements.

Programmatically:

• fibonacci(0) = 0
• fibonacci(1) = 1
• fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

Given n, return the n^th number in the sequence.

As an example, n = 5. The Fibonacci sequence to 6 is fs = [0, 1, 1, 2, 3, 5, 8]. With zero-based indexing, fs[5] = 5

 

Recursion: Fibonacci Numbers | HackerRank

 

풀이

function fibonacci(n) {
    if(n === 0) return 0;
    if(n === 1) return 1;

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

생각보다 너무 간단해서 허무쓰....

재귀함수로 이전값과 전전값을 더해준 걸 리턴해주면 끝.

단, 0과 1은 각각 0과 1을 반환함.

 

 

다른 사람의 풀이

const fibonacci = (n, cache = {}) => {
  if (n < 0 || n === undefined) return null;
  if (n < 2) return n;
  if (cache[n]) return cache[n];
  cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
  return cache[n];
};

재귀함수를 이용했는데, n이 음수이거나 정의되지 않았을 때를 처리해줬고, 내가 if문 두개로 나눠쓴 것을 n < 2일 때, n을 반환하는 식으로 한 번에 처리함.

 

const fibonacci = n => {
  let previous = 0;
  let current = 1;
  if (n < 0 || n === undefined) return null;
  if (n < 2) return n;
  for (let i = 1; i < n; i++) {
    let temp = current;
    current = current + previous;
    previous = temp;
  }
  return current;
};

같은 사람의 다른 풀이인데, 재귀함수를 이용하지 않고, previous와 current 변수를 만들고 for문을 돌려 처리를 함.

작성자피셜 : "Better solution since it has a constant space complexity but still has linear time complexity"