재귀함수를 이용해 분할 및 정복 알고리즘 구현하기

반응형

재귀 프로그래밍을 배우는 첫 번째 단계는 재귀 프로그래밍을 배우는 것이다.

내가 거기서 뭘 했는지 봤지?

대답할 경우 === "예"
"읽다"를 반환하다.
그렇지 않으면
ReturnToStart()
종지부를 찍다

 

재귀란 무엇인가?

재귀의 정의는 꽤 간단하다: 자신을 부르는 함수.
암호로 처음 접하는 건 마법처럼 보일지도 몰라 만약 그날 우리의 마술 능력이 떨어진다면, 그것은 실수처럼 보일 수도 있다.

반복적인 문제 해결을 이해하는 유용한 방법 중 하나는 반복적인 문제 해결(루프 사용)과 비교하는 것이다. 재귀로 해결할 수 있는 많은 문제는 루프를 사용하여 해결할 수 있다.

 

우리가 루프를 사용할 수 있다면 왜 그 안에 있는 함수를 불러야 할까요? 예를 들어 성능에 있어서는 반복 솔루션이 재귀 솔루션보다 더 효율적일 수 있습니다. 그래서 뭐가 문제야?

재귀 기능을 구현하면 코드를 쉽게 읽고 쓸 수 있습니다(일부에서는 "인간 프로그래머 성능"이라고 부르는 것을 얻을 수 있음). 코드는 쓰여진 것보다 훨씬 더 많이 읽히기 때문에 우리의 논리를 따라 하기 쉽게 만드는 것은 미래의 오류가 발생할 여지가 적다.

게다가, 재귀 함수는 함수 호출 반환을 저장하기 위해 호출 스택을 이용한다. 이와 같은 로직을 반복적으로 구현하는 것은 당신이 수동으로 스택을 만들고, 말하자면 휠을 재발명하고, 내장된 콜 스택을 이용하는 것보다 버그가 발생하기 쉬운 방법을 필요로 할 것이다. 반복 기능 내에서 재귀 현상을 시뮬레이션하는 자신을 발견하면 회피하려는 바로 그 기능적 간접 비용을 다시 도입하는 것일 수 있습니다.

반복적인 문제 해결을 재귀적인 문제 해결과 비교하는 것은 우리가 재귀가 어떻게 작동하는지를 이해하는 데 유용한 방법이지만, 실제로 더 자세히 살펴보면, 순전히 1:1 수준에서 반복적인 문장과 비교하는 것을 어렵게 만드는 재귀 함수의 측면들이 있다. Tail call을 사용하여 재귀 최적화 또는 함수형 프로그래밍 언어는 루프가 내장되어 있지 않기 때문에 재귀가 필요하다는 사실).

그러나 이러한 주제는 본 소개 기사의 범위를 벗어나며, 우리의 비교는 여기에서 도움이 될 것입니다.

 

재귀는 어떻게 작동합니까?

재귀의 비유로서 종종 주어지는 이미지는 러시아의 둥지 인형이다. 만약 여러분이 그들을 전에 본 적이 없다면, 이것이 작동되는 방식입니다: 하나의 인형으로 보이는 것이 열려 같은 인형이지만 그 안에 있는 더 작은 인형이 드러납니다. 그리고 나서 그 인형은 같은 인형이지만 더 작은 인형도 드러내고, 열리지 않는 아주 작은 인형에 닿을 때까지 계속해서 드러낸다.

각각의 인형은 가능한 가장 작은 인형에 도달할 때까지 이전의 인형과 동일한 인형을 포함합니다.

 

인형은 내부로부터 스스로를 부르는 우리의 기능과 같으며, 주어진 문제에 대해 가능한 가장 작은 데이터 세트에 도달할 때까지 우리의 데이터 세트는 매번 작아집니다.

재귀 함수를 구성하는 두 가지 중요한 부분이 있는데, 기본 대소문자와 재귀 대소문자가 그것이다.

앞에서 사용한 모든 정수를 더하는 합계함수()를 분해하자. 참고: 이 가이드에 나와 있는 모든 예제에 JavaScript를 사용하고 있지만 개념만 파악하면 이러한 예제를 사용자가 선택한 프로그래밍 언어로 변환하는 것은 어렵지 않습니다.

우리의 논리대로라면 베이스 케이스가 먼저다. 그것은 우리의 가장 작은 둥지 인형과 같습니다. 가장 작은 하위 문제에 도달하면 함수가 반환되어야 하므로 각 함수 호출에서 기본 케이스의 조건을 충족했는지 확인하는 것이 우선입니다. 이 함수에서는 array.length === 1인지 확인하고, 그렇다면 데이터 집합의 마지막 정수까지 내려가 어레이[0]에 있는 정수를 반환해야 합니다.

 

베이스 케이스의 조건이 충족되면, 좋아요, 그럼 복귀를 시작하죠. 그렇지 않으면, 우리는 함수를 다시 호출하지만 이번에는 더 작은 데이터 세트로 호출한다. 우리의 합계() 함수는 이제 베이스 케이스에 도달할 때까지 이 패턴으로 계속됩니다. array.pop()을 사용하는데, array는 배열의 마지막 항목을 제거하고 반환하여 배열이 sum()으로 두 번째로 전달되기 전에 하나의 정수 더 작게 만듭니다. array.pop()의 작동 방식에 대한 자세한 내용은 이 항목을 참조하십시오.

호출 스택

이 패턴은 "다른 함수를 호출할 때마다 어떻게 변수를 추적하는지" 궁금할 수 있습니다. 대답은 다음과 같습니다.
콜 스택.

 

MDN 웹 오피스에 따르면:

함수를 호출할 때마다 호출 스택에 추가됩니다. 우리가 다른 함수 내부에서 함수를 호출할 때, 우리가 호출하고 있는 원래 함수는 부분적으로 완료된 상태에서 일시 중지된다. 지금 호출하는 함수가 돌아올 때까지 기다려야 한다.

이러한 각 함수의 변수들은 메모리에 저장되며, n과 같은 변수가 스택의 각 수준에서 무엇을 나타내는지를 추적한다. 작업 중인 데이터의 크기에 따라 콜 스택이 매우 커지고 메모리가 많이 소모될 수 있으며, 선택하지 않을 경우 프로그램 속도가 느려질 수 있습니다. (후계 호출 최적화를 통해 이를 방지할 수 있습니다.)

각 함수 호출이 호출 스택에 추가되면, 재귀 함수에 기본 대소문자를 포함하는 것을 잊으면 어떻게 됩니까?

 

우리가 새해를 맞이하는 카운트다운 기능을 만들고 있다고 상상해 보세요. 함수를 재귀적으로 호출했지만 기본 대소문자를 포함하지 않았다고 가정합시다.

만약 우리가 이 코드를 실행한다면 스택 오버플로라고 불리는 것을 일으킬 수 있다; 우리의 함수 호출은 무한 루프에 걸린다. 이렇게 하면 사용 가능한 메모리가 소진되고 브라우저가 충돌할 때까지 스택에 기능이 계속 추가됩니다.

이 예에서 재귀 기능을 활용하려면 항상 기준 케이스를 포함해야 합니다!

 

재귀 요인 함수

여기서 배운 모든 것을 하나로 묶기 위해 주어진 정수의 계수를 계산하는 재귀 함수를 만들어 보자. 수학에서, 음이 아닌 정수 n의 요인(factor)은 n보다 작거나 같은 모든 양의 정수의 곱이다. 이것은 n으로 표시됩니다!

예를 들어 5!는 다음과 같이 쓸 수 있다.

5! = 5 x 4 x 3 x 2 x 1 = 120

 

6!와 9!는 다음과 같다.

6! = 6 x 5 x 4 x 3 x 2 x 1 = 720
9! = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362880

보시다시피 이러한 계산된 값은 매우 빠르게 커지기 시작합니다.

그렇다면, 왜 인자를 계산할 수 있는 능력이 우리에게 유용할까요?
우선, 팩토리얼은 우리가 얼마나 많은 다른 방법들을 배열하고 결합할 수 있는지를 세려고 할 때마다 매우 유용하다. 만약 우리가 얼마나 많은 방법으로 n개의 것들을 배열할 수 있는지 결정하려고 한다면, 우리는 첫 번째로 n개의 선택부터 시작해야 합니다. 첫 번째 항목을 선택한 후에는 두 번째 항목에 대해 (n-1)개의 선택사항이 남아 있으며, 선택사항이 부족해질 때까지 각 항목을 계속 사용하게 됩니다. 이것은 n으로 표현될 수 있는 문제입니다!

요인 함수의 또 다른 사용 사례는 항목 집합에서 항목을 선택할 수 있는 방법을 결정하는 것입니다. 어떤 식으로든 이 두 가지 예시를 포함하는 많은 알고리즘 문제들이 있는데, 아마도 여러분은 이 설명에 맞는 몇 가지 실제 문제들을 보았거나 생각할 수 있을 것이다.

 

재귀 요인 예제

우리의 요인 함수를 가져와서 코드로 적읍시다.

요약하자면, 우리는 이것을 적절한 재귀 함수로 만들기 위해 다음과 같은 것들이 필요하다는 것을 알고 있다.

-베이스 케이스
-및 재귀 사례

 

우리의 기본 사례는 우리 계산의 종료를 알리는 것이고 우리의 호출 스택에서 처음으로 완료된 함수를 반환하는 것이다. 위의 정의에 따르면:

음이 아닌 정수 n의 요인은 n보다 작거나 같은 모든 양의 정수의 곱입니다.

우리는 n부터 카운트다운하는 마지막 양의 정수를 치면 계산이 완료되었다는 것을 알 수 있을 것이다. 글쎄, 꼭 그렇진 않아…

수학적으로 정확히 말하자면, 만약 우리가 5를 쓴다면, 그것은 다음과 같을 것이다:

5!-4!-3!-2!-1!-0! 여기서 0! = 1

 

그러면 머리가 긁힐 수도 있어요. 0에 0을 곱하면 0이 되는 거 아닌가요? 팩토리얼에 관한 한 그렇지 않아요. 이를 이해하기 위한 가장 좋은 방법은 위에서 설명한 팩토리얼의 사용 사례를 되돌아보는 것입니다. ZERO 항목을 사용하여 얼마나 많은 조합을 만들 수 있는지 계산하려고 한다면 선택할 수 있는 솔루션이 하나뿐이며 이는 해결책이 아닙니다.

때때로 1을 기본 대소문자로 사용하는 재귀 요인 함수를 볼 수 있고, 여전히 동일하게 계산되지만, 이 예에서는 0을 사용할 것입니다.

함수의 상단에서 n === 0인지 확인하고, 0이면 1을 반환하려고 합니다.

베이스 케이스는 그것만 있으면 됩니다. 우리는 우리의 함수 호출이 무한 루프가 되지 않도록 이 조건이 우리의 재귀적인 경우 앞에 나타나는지 확인할 필요가 있다!

 

다음은 재귀 사례를 작성하겠습니다. 이 경우 작성이 간단하여 현재 n 값에 요인 함수를 곱한 값이라고 하지만 현재 n 값보다 1 작은 값을 사용합니다.

그게 우리가 필요한 전부야! 크롬 콘솔에 함수를 복사하고 factor(5)를 호출하면 120이 되는 것을 알 수 있습니다.

우리가 위에서 계산한 것을 고려할 때 정확히 우리가 예상하는 것은 다음과 같다.
5! = 5 x 4 x 3 x 2 x 1 = 120

 

6번! 9번!

위에서 계산한 대로 각각 720과 362880을 얻었습니다.

6! = 6 x 5 x 4 x 3 x 2 x 1 = 720
9! = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362880

대단해! 이 기능은 간단하게 쓰여져 있고 읽을 때 이해하기 쉽습니다.

 

요인 함수 호출 스택

마지막으로 자세히 설명드리자면, 우리의 재귀 요인 함수 호출이 어떻게 우리의 호출 스택에 표시되는가 입니다. 만약 우리가 우리의 요인함수에서 일어나는 일을 유사 코드로 쓴다면, 다음과 같이 보일 것이다.

n의 서로 다른 값이 각 수준에서 저장되고 n의 각 값은 호출 스택의 해당 수준에서만 사용할 수 있습니다.
factor()는 아래쪽으로 반복되는 것처럼 보이지만, 호출 스택에 일어나는 일을 시각화하는 더 나은 방법은 이 코드를 거꾸로 뒤집는 것입니다.

 

이것은 위와 같은 것을 나타내지만, 새로운 함수 호출을 할 때마다 스택의 맨 위에 추가하고 있습니다. 맨 아래에 있는 호출은 스택에 남아있고, 정지된 상태로 위에 있는 호출이 돌아오기를 기다리며 계산하고 반환할 수 있습니다.

factor(0)는 기본 사례이며 숫자 1을 반환하여 반환되는 첫 번째 호출입니다.

스택은 LIFO(Last-in First-Out) 기반으로 동작하며, 호출되는 마지막 함수가 스택에서 가장 먼저 제거된다. 이제 최상위 함수가 반환되었으므로 스택의 상단에서 반환된 값을 다음과 같이 스택의 다음 함수로 전달할 수 있습니다.

우리의 요인(1)은 이제 계산을 완료하고 스택 위에서 튀어나와 값 1을 다음 함수로 전달하는 데 필요한 값을 가진다.

 

우리는 원래의 함수 호출에 도달할 때까지 스택에서 튀어 나왔다가 돌아오는 패턴을 계속합니다.

 

다시 원래의 통화로 돌아갔는데, 120번은 이전과 마찬가지로 응답하여 콜 스택을 정리합니다.

이제 재귀 기능을 사용하면 함수와 호출 스택 사이에서 일어나는 대화를 시각화할 수 있으므로 이면에서 어떤 일이 벌어지는지 파악할 수 있습니다.

분열과 정복!

분할 및 정복 문제 해결 전략은 정의상 재귀적이다. 알고리즘적으로 해결하고자 하는 문제와 과제에 직면할 때 다음과 같은 질문을 함으로써 두통을 줄일 수 있습니다. "이 문제를 작은 문제로 나누고 각각의 작은 문제를 해결할 수 있을까요?"

 

분열과 정복 패러다임에 익숙해지면 알고리즘적으로 생각을 시작하는 데 도움이 될 것이다. 그것은 겉보기에는 힘들고 복잡해 보이는 문제들을 해결하기 위해 서로를 기반으로 하는 작고 이해할 수 있는 단계들로 나눌 수 있도록 도와줄 것이다.

이러한 문제 프레임 방식은 알고리즘으로 여정을 시작하기 좋은 장소이며, 여기서 얻은 재귀에 대한 이해를 통해 오늘날 문제 해결에 분할 및 정복 전략을 구현하는 연습을 할 수 있습니다.

이봐, 이 가이드가 너에게 도움이 되었기를 바라며 너의 피드백을 환영해!

해피 코딩!