JavaScript에서 피보나치 수열 구현: 일반적인 접근 방식 및 변형

개발자라면 피보나치 수열의 값을 계산하는 함수를 작성하는 작업에 직면했을 것입니다. 이 고전적인 문제는 코딩 인터뷰에서 자주 나타나며 일반적으로 재귀적 구현을 ​​요구합니다. 그러나 면접관은 때때로 특정 접근 방식을 요청할 수 있습니다. 이 기사에서는 JavaScript에서 가장 일반적인 피보나치 수열 구현을 살펴보겠습니다.

피보나치 수열이란 무엇입니까?

먼저 기억을 되새기자. 피보나치 수열은 각 숫자가 이전 두 숫자의 합인 일련의 숫자입니다. 0과 1로 시작합니다:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

일반적인 구현 접근 방식

1. 재귀적 접근

가장 전통적인 요청은 재귀 구현입니다.

function fibonacciRecursive(n) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

이 접근 방식은 간단하지만 큰 n 값에는 성능이 좋지 않습니다. 16GB RAM을 탑재한 MacBook Pro i9에서 40번째 피보나치 수를 계산하는 데 약 1.5초가 걸렸습니다.

console.time('Recursive');
fibonacciRecursive(40);
console.timeEnd('Recursive');

VM379:3 Recursive: 1521.569091796875 ms

50번째 숫자를 계산하려고 하면 Chrome 탭이 응답하지 않습니다.

2. 캐싱을 통한 재귀적 접근(메모이제이션)

이 질문의 다음 변형은 재귀 구현에 캐싱 메커니즘을 추가하여 성능을 향상시키는 것입니다.

function fibonacciCached(n, cached = {[0]: 0, [1]: 1}) {
  if (n < 1) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  if (cached[n]) {
    return cached[n];
  }

  cached[n] = 
    fibonacciCached(n - 1, cached) + fibonacciCached(n - 2, cached);

  return cached[n];
}

이 접근 방식은 초기 값이 0과 1인 캐시된 객체를 도입합니다. 특정 숫자에 대해 먼저 피보나치 값을 이미 계산했는지 확인합니다. 그렇다면 다시 계산하는 대신 캐시된 결과를 반환합니다. 그렇지 않으면 해당 값을 계산하여 캐시에 저장합니다.

성능 향상이 상당합니다(물론 추가 메모리 사용으로 인해). 40번째 피보나치 수를 계산하는 데 ~0.02ms가 걸렸습니다.

console.time('Recursive, with caching');
fibonacciCached(40);
console.timeEnd('Recursive, with caching');

VM382:3 Recursive, with caching: 0.01806640625 ms

3. for 루프를 사용한 반복 접근 방식

또 다른 일반적인 변형은 for 루프를 사용하여 피보나치 수열을 구현하는 것입니다.

function fibonacciWithIteration(n) {
    if (n <= 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }

    let prev = 0;
    let next = 1;
    let result = 1;

    for (let i = 2; i <= n; i++) {
        result = prev + next;
        [prev, next] = [next, prev + next];
    }
    return result;
}

이 접근 방식은 기본 재귀 방법(캐싱이 없는 방법)보다 훨씬 빠릅니다.

console.time('With iteration');
fibonacciWithIteration(40);
console.timeEnd('With iteration');

VM44:22 With iteration: 0.10107421875 ms

반복 접근 방식은 매우 큰 입력 값을 효율적으로 처리할 수 있습니다.

console.time('With iteration');
const result = fibonacciWithIteration(1400);
console.log(result);
console.timeEnd('With iteration');

VM325:22 1.7108476902340223e+292
VM325:23 With iteration: 0.5830078125 ms

보너스: 피보나치 수열을 배열로 반환

면접관은 전체 피보나치 수열을 n번째 숫자까지 배열로 반환하도록 요청할 수도 있습니다. 재귀적 접근 방식과 반복적 접근 방식을 모두 사용하여 이를 구현해 보겠습니다.

재귀적 접근

function fibonacciSequence(n) {
  if (n === 0) {
      return [0];
  }
  if (n === 1) {
      return [0, 1];
  }

  const arr = fibonacciSequence(n - 1);
  const currentValue = arr[n - 1] + arr[n - 2];

  return [...arr, currentValue];
}

console.log(fibonacciSequence(5)); // [0, 1, 1, 2, 3, 5]

이 기능은 다음과 같이 작동합니다.

1. 0과 1의 경우 하드코딩된 배열을 반환합니다.
2. 기타 경우:

• 이전 번호의 시퀀스를 가져와서 arr에 저장합니다.
• arr의 마지막 두 값을 합산하여 currentValue를 계산합니다.
• arr과 currentValue를 새로운 배열로 결합하여 반환합니다.

반복적 접근

function fibonacciSequenceWithIteration(n) {
  if (n < 1) {
    return [0];
  }

  let prev = 0;
  let next = 1;
  const arr = [prev, next];

  for (let i = 2; i <= n; i++) {
    arr.push(prev + next);
    [prev, next] = [next, prev + next];
  }
  return arr;
}

console.log(fibonacciSequenceWithIteration(5)); // [0, 1, 1, 2, 3, 5]

이 기능은 다음과 같이 작동합니다.

1. 입력이 0이면 요소 0만 포함된 배열을 반환합니다.
2. 기타 경우:

• 이전 값과 다음 값을 저장하기 위해 prev와 next 변수를 초기화합니다.
• 초기값 [0, 1]을 사용하여 arr을 생성합니다.
• 2부터 n까지 반복하며 각 반복에서 prev와 next의 합을 arr로 푸시합니다.
• 이전 값과 다음 값을 업데이트하고 다음 반복을 계속합니다.

결론

이 문서에서는 몇 가지 일반적인 피보나치 수열 구현을 다루지만 전체 목록은 아닙니다. 인터뷰나 작업에서 다른 변형을 발견했다면 댓글로 공유해주세요!

최신 JavaScript 및 소프트웨어 개발 소식을 받아보세요! 더 많은 통찰력과 토론을 보려면 내 Telegram 채널에 가입하세요: TechSavvy: 프런트엔드 및 백엔드.

위 내용은 JavaScript에서 피보나치 수열 구현: 일반적인 접근 방식 및 변형의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!