[JavaScript] 피보나치 수 구하기

피보나치 수 구하기 문제를 이번에 다시 풀 기회가 있었는데 다시 잠시 망설이는 스스로를 발견.

구하는 몇 가지 방식을 정리 해봅니다.

 

---

 

피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다. -위키백과-

 

피보나치 수를 이어서 써보면

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 와 같이 진행된다.

2 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 점화식.

 

문제

정수 n이 입력되었을 때, fibonacci 함수를 제작하여 n번째 피보나치 수를 반환하시오.

 

1. 숫자 2개를 선언하고, 그 합을  반복해서 구하기

function fibonacci(n) {

  if (n <= 2) { 
    return 1;  //2번째 까지의 값은 1이므로 1을 리턴
  }
  
  let i = 1
  let num1 = 0;
  let num2 = 1;
  let result;
  
  while (i < n) {  //숫자 n이 될때까지 반복
    result = num1 + num2;
    num1 = num2;
    num2 = result;
    i++;
  }
  return result;
}

 

2. 재귀를 활용해서 구하기. 재귀를 두 번 호출한다.

function fibonacci(n) {

  if (n < 2) {
    return n; //2보다 작은 수는 그 값을 리턴하므로 조건을 생성
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

 

여기서 문제를 n번째 까지의 수열을 리턴하시오. 라고 한다면,

function fibonacci(n) {

  if (n <= 2) { 
    return 1;  
  }
  
  let i = 1
  let num1 = 0;
  let num2 = 1;
  let result = [];  //결과값을 담을 빈 배열을 선언하고
  
  while (i < n) {  
    let sum = num1 + num2;
    result.push(sum)  //값이 나올때마다 배열에 푸시
    num1 = num2;
    num2 = sum;
    i++;
  }
  return result.join(', ');
}

 

메모이제이션 하는 코드도 추가할 예정.

재귀는 한번 더 살펴봐야겠다.

 

---

 

힘이 들 땐 명상을 합니다.