일반적인 재귀 인터뷰 도전

안녕 모두들! 매주 공개되는 일련의 코딩 과제 및 직업 관련 콘텐츠인 Code Review에 다시 오신 것을 환영합니다. 연휴 기간 동안 잠시 휴식을 취했지만, 2020년에 우리가 가진 모든 것을 보여줄 준비가 되어 돌아왔습니다. Coderbyte의 우리 팀은 일상 업무에서 떨어져 있는 여분의 시간을 감안하여 해킹을 해왔으며 2020년에 몇 가지 큰 일을 계획하고 있습니다.

뉴스레터 📫

먼저, 우리의 새로운 뉴스레터를 언급하게 되어 기쁩니다! 우리는 큰 것을 발표할 때마다 작은 기능 공개 스니펫을 보낼 것이므로 우리 커뮤니티는 우리가 새로운 것을 출시할 때 가장 먼저 알게 됩니다. Give us your email here 그리고 우리는 당신을 "처음 알게 된"목록에 추가할 것입니다 :) 이번 주 챌린지를 시작해 봅시다. 2020년을 응원합니다! 🎉

문제:

무한한 양의 쿼터, 다임, 니켈, 페니가 주어지면 n센트를 동전으로 표현하는 방법의 수를 반환하는 함수를 작성하세요.

재귀에 관한 몇 가지 팁

재귀는 때때로 압도적일 수 있습니다. 재귀 문제에 접근할 때 진정으로 긴장을 푸는 데 도움이 되는 것은 정의에 따라 재귀 솔루션이 더 작은 하위 문제에 대한 솔루션으로 구성된다는 점을 기억하는 것입니다.

고전적인 "n 번째 피보나치 수 계산"과제를 수행하십시오. 피보나치 수열은 각 숫자가 0과 1부터 시작하여 앞의 두 숫자의 합인 일련의 숫자입니다. 상향식 접근 방식을 취할 수 있습니다. 간단한 경우에 대한 문제를 해결하고 거기에서 빌드합니다. 이 문제에 대한 가장 간단한 경우는 시리즈의 정의에 따라 0을 반환하는 피보나치 시리즈의 0번째 숫자를 얻는 것입니다. 정의에 따라 1을 반환하는 첫 번째 숫자를 얻기 위해 이를 기반으로 구축해 봅시다. 피보나치 수열의 두 번째 수를 계산하기 위해 0과 1을 더하면 또 다른 1이 나옵니다. 세 번째 수를 계산하려면 1과 1을 더하면 2가 됩니다. 그리고 수열은 다음과 같이 계속됩니다0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... .

이는 다음과 같이 요약할 수 있습니다. fibonacci(0)는 항상 0입니다. fibonacci(1)는 항상 1입니다. 그 후, fibonacci(n)는 fibonacci(n-1) 및 fibonacci(n-2)로 알려진 앞의 두 숫자의 합입니다.

이 문제에서 n가 1일 때 항상 1을 반환하고 n가 0일 때 0을 반환하는 것이 기본 사례이며 문제를 세분화할 수 있는 가장 작은 하위 문제로 생각할 수 있습니다.

코드에서 다음과 같이 표시됩니다.

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

빅오

종종 재귀 솔루션의 Big-O를 찾기 위해 코드 경로를 재귀 트리로 그리는 데 도움이 됩니다. 위 예의 경우:



규칙은 다음과 같습니다. 각 노드가 트리에 있는 가지의 수는 전력의 기본이고 트리의 수준은 지수입니다. 따라서 이 예에서 Big-O는 각 함수 호출이 2개의 함수 호출로 분할되기 때문에 O(2^n)입니다. 그리고 트리의 레벨 수는 n 에 해당합니다.

모두 즐거운 시간 보내시고 솔루션과 새로운 도전으로 다음에 만나요!