Java에 대한 기능적 접근 방식

12장. 재귀

이 작품은 AI를 사용하여 번역되었습니다. 여러분의 피드백과 의견을 환영합니다: [e-mail]

재귀는 문제를 더 작은 버전으로 나눌 수 있는 문제 해결 접근 방식입니다. 많은 개발자는 재귀를 반복 기반 문제 해결의 또 다른 복잡한 접근 방식으로 생각합니다. 하지만 특정 문제 그룹에 대해 기능적으로 다양한 기술을 알고 있는 것이 좋습니다.

이 장에서는 재귀의 일반적인 개념, 재귀 메서드를 구현하는 방법, 다른 형태의 반복과 비교하여 Java 코드에서 재귀가 차지하는 위치에 대해 설명합니다.

재귀란 무엇인가요?

'재귀'에서 입력 매개변수보다 작거나 같은 모든 양의 정수의 곱인 계승을 계산하는 예시를 보았습니다. 많은 책, 가이드, 튜토리얼에서 재귀를 설명할 때 계승을 사용하는 이유는 부분적으로 풀기에 완벽한 문제이며, 이 장의 첫 번째 예시이기도 하기 때문입니다.

계승 계산의 모든 단계는 입력 매개변수의 곱과 다음 계승 연산 결과로 나뉩니다. "1"로 정의된 fac(1)에 도달하면 계산이 종료되고 이전 단계에 값을 제공합니다. 전체 단계는 방정식 12-1에서 볼 수 있습니다.

방정식 12-1. 계승 계산의 공식적인 표현

$$\begin{array}{c}fac\left(n\right)\hfill \\ \hfill \to & n*fac(n-1)\hfill \\ \hfill \to & n*(n-1)*fac(n-2)\hfill \\ \hfill \to & n*(n-1)*(n-2)*\cdots *fac\left(1\right)\hfill \\ \hfill \to & n*(n-1)*(n-2)*\cdots *1\hfill \end{array}$$

이러한 계산 단계의 일반화는 동일한 문제의 작은 인스턴스를 결합하여 문제를 해결하는 재귀의 기본 개념을 시각화합니다. 이는 기본 조건에 도달할 때까지 수정된 인수로 자신을 호출하는 메서드를 사용하여 수행됩니다.

재귀는 두 가지 다른 연산 유형으로 구성됩니다:

기본 조건

기본 조건은 실제 값을 반환하고 재귀 호출 체인을 풀어주는 미리 정의된 경우(문제에 대한 해결책 )로, 이전 단계에 해당 값을 제공하여 이제 결과를 계산하고 이전 단계로 반환하는 등의 작업을 수행할 수 있습니다.

재귀 호출

호출 체인이 기본 조건에 도달할 때까지 모든 단계는 수정된 입력 매개변수로 자신을 호출하여 또 다른 호출 체인을 생성합니다.

그림 12-1은 재귀 호출 체인의 일반적인 흐름을 보여줍니다.

그림 12-1. 작은 문제로 문제 해결

가장 작은 부분에 대한 해결책을 찾을 때까지 문제는 점점 작아지고, 이 해결책은 다음 큰 문제에 대한 입력이 되며, 모든 부분의 합이 원래 문제에 대한 해결책을 구축할 때까지 계속됩니다.

헤드 대 테일 재귀

재귀 호출은 메서드 본문에서 재귀 호출의 위치에 따라 헤드 재귀와 테일 재귀의 두 가지 범주로 나뉩니다:

헤드 재귀