JavaScript에서 재귀 알고리즘을 구현하는 방법 소개

이 글은 JavaScript로 재귀 알고리즘을 구현하는 방법을 소개합니다. 참고할 만한 가치가 있으니 도움이 필요한 분들에게 도움이 되길 바랍니다.

먼저 정의를 살펴보겠습니다. 재귀 알고리즘은 문제를 크기가 감소된 동일한 유형의 하위 문제로 변환하고 각 하위 문제는 동일한 알고리즘을 사용하여 해결됩니다. 일반적으로 재귀 알고리즘은 하위 문제를 해결하기 위해 자신을 호출하는 함수입니다.

재귀 알고리즘의 특징:

1. 함수 프로세스 중에 자신을 호출합니다.
2. 재귀 과정에서는 재귀의 종료, 즉 재귀 종료를 판단하기 위한 명확한 조건이 있어야 합니다.
3. 재귀 알고리즘은 간단하지만 비효율적이어서 일반적으로 권장 알고리즘으로 권장되지 않습니다.

위 내용은 바이두 백과사전의 설명이며, 예를 들어 자세히 살펴보시기 바랍니다.

　Factorial

　문제 설명: n! = n*(n-1)*...2*1

　코드 구현:

　문제가 발생하면 정의를 따릅니다. 먼저 유사한 하위 문제로 규모를 줄일 수 있습니다. 예를 들어, n!은 n* (n-1)!과 같습니다. 그러면 (n-1)! = (n-1)*(n-2)!입니다. if가 종료될 때까지 이 순서대로 아래로 누릅니다. 여기서는 인수.callee를 사용하여 함수 이름의 긴밀한 결합을 방지합니다. 여기서는 계승(n-1)과 동일합니다. 함수 구현이 간단하고 명확합니까? 물론 문제의 규모가 단순하기 때문에 실제로 루프를 이용해 구현해 볼 수도 있다.

피보나치 수열

　문제 설명: 1, 1, 2, 3, 5, 8, 13, 21, 34, ..... n번째 숫자를 찾으세요.

　코드 구현:

　

　사실 지금 당장 아이디어를 구현하는 것은 매우 간단합니다. 분석을 통해 처음 두 숫자의 합인 n번째 숫자를 얻을 수 있습니다. 이를 통해 조건 n

　계단 문제를 풀어보세요

　계단에는 n개의 계단이 있습니다. 한 계단에 1계단 올라갈 수도 있고, 한 계단에 2~3계단 올라갈 수도 있습니다.

　코드 구현:

　

　이것은 실제로 피보나치 수열의 구현입니다. 분석할 때 이를 소규모 하위 클래스 문제로 변환할 수 있습니다. 지정된 사다리의 마지막 단계에 도달하면 세 가지 상황이 있을 수 있습니다. 하나는 한 단계 올라가고, 두 개는 두 단계 올라가고, 세 번째는 세 단계 올라갑니다. 따라서 전체 방법은 F(n) = F(n-1) + F(n-2) + F(n-3)입니다. 그러면 자연스럽게 그들만의 소소한 계산이 되고, 판단 조건이 발생할 때까지 순환이 계속된다.

　최대 공약수

　문제 설명: 두 숫자가 주어졌을 때 두 숫자가 같을 경우 최대 공약수는 그 자체입니다. 같지 않으면 두 숫자의 뺄셈의 절대값을 취하여 두 숫자 중 가장 작은 숫자와 비교합니다. 두 숫자가 같지 않으면 위의 알고리즘을 계속합니다. 동등해질 때까지.

　코드 구현:

　

　특별히 말할 것도 없고, 문제 설명에서 요구하는 대로 구현하면 됩니다. 재귀의 종료는 a가 b와 같다는 것입니다.

　하노이 타워

　문제 설명: 다들 어느 정도 플레이해 봤기 때문에 여기서는 자세히 설명하지 않겠습니다.

　 코드 구현:

　

재귀의 본질을 깨닫기 전에는 단순히 이 문제 때문에 당황했습니다. 나는 계속해서 스스로에게 묻습니다. 다음에 어디로 가야 할지 어떻게 알 수 있나요? 나중에 나는 실제로 마지막 문제를 어떻게 처리할지에 대해 더 걱정하고 있다는 것을 깨달았습니다. 이것을 어떻게 말합니까? 처음부터 디스크가 하나만 있으면 C열이나 B열로 이동할 수 있다고 생각할 수 있습니다. 당연히 두 개의 디스크로도 가능합니다. 디스크 3개면 괜찮습니다. 그럼 4디스크의 상황에 대해 말씀드리겠습니다. 4개의 디스크를 완성하려면 A의 디스크가 C로 완전히 전송되어야 합니다. 처음 세 개의 디스크를 전체적으로 B에 넣은 다음 네 번째 디스크를 C로 이동할 수 있습니다. 그런 다음 처음 세 개의 디스크를 C에 넣었는데 성공했습니다. 처음 세 게임은 새로운 게임으로 처리될 수 있고, 처음 두 게임은 전체로 처리될 수 있습니다. 이런 식으로 우리는 전체적인 큰 일에만 신경 쓰면 되고, 다른 일은 작은 문제로 해결될 수 있습니다.

이분법빠른 정렬

문제 설명: 이분법 방법을 사용하여 배열을 작은 것부터 큰 것까지 정렬합니다.

　코드 구현:

　

글쎄... 이번이 두번째로 쓰는 글이네요. 이번에는 재귀 구현이 지난번보다 훨씬 명확해졌습니다. 사실 큰 규모를 작은 규모로 축소하고, 큰 전체를 배려하며, 계속해서 작은 규모로 축소하여 계산하도록 하는 것이기도 합니다. 자세한 내용은 원문을 확인하실 수 있습니다.

DOM 트리의 재귀

문제 설명: 한 노드의 모든 상위 노드에 대한 tagName을 가져옵니다.

코드 구현:

　　

아마도 이해할 수 있을 것이므로 아무 말도 하지 않겠습니다. 이전 하노이 타워 및 Quick Sort와 비교하면 이것은 매우 간단하지만 JavaScript의 실제 적용에 가장 가깝습니다.

이 기사는 여기서 끝났습니다. 더 흥미로운 콘텐츠를 보려면 PHP 중국어 웹사이트의 JavaScript Video Tutorial 칼럼을 주목하세요!

위 내용은 JavaScript에서 재귀 알고리즘을 구현하는 방법 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!