재귀를 배우고 나면 그 개념 자체는 이해할 수 있지만, 실제로 문제를 재귀적으로 풀어내는 것은 쉽지 않은 일이다. 이는 우리가 일상생활에서 재귀적으로 사고할 일이 거의 없기 때문이다. 하지만 재귀에도 몇 가지 주요 패턴이 존재하며, 이를 이해하고 연습한다면 어떤 문제가 재귀에 적합한지 파악하고 효과적으로 해결할 수 있는 ‘눈’을 키울 수 있다
첫 번째 패턴: 단순 반복 실행
가장 기본적인 재귀 패턴은 단순히 반복적인 작업을 수행하는 것이다. 앞서 1부터 3까지 숫자를 세는 예시를 통해 이미 경험했다
두 번째 패턴: 하위 문제 기반 계산 (하향식 사고)
재귀의 진정한 위력은 하위 문제의 결과를 기반으로 현재 문제를 계산하는 방식, 즉 하향식(Top-Down) 사고에서 발휘된다. 이는 큰 문제를 작은 하위 문제로 쪼개고, 그 하위 문제가 결과가 이미 해결되었다고 가정한 뒤 현재 문제를 해결하는 방식이다. 팩토리얼 함수 구현에서 이를 경험했다.
팩토리얼 재귀 함수의 핵심
public class FactorialRecursion {
public static int factorial(int number) {
if (number <= 1) {
return 1;
} else {
// 하위 문제 (factorial(number - 1))의 결과를 기반으로 현재 문제 계산
return number * factorial(number - 1);
}
}
// ... (main 메서드 생략)
}
여기서 return number * factorial(number – 1); 구문은 (number – 1)!의 결과에 number를 곱하여 number!를 계산하는 것이다. 즉, number가 5일때, 4!의 결과에 5를 곱하는 방식으로 현재 문제(5!)를 해결한다. 하지만 팩토리얼은 재귀 함수를 사용하지 않고 반복문으로도 구현할 수 있다
for문을 이용한 팩토리얼 구현
public class FactorialLoop {
public static int factorial(int number) {
int result = 1;
for (int i = 1; i <= number; i++) {
result *= i;
}
return result;
}
// ... (main 메서드 생략)
}
이 반복문 방식은 1부터 number까지 순차적으로 곱하면서 결과를 쌓아가는 상향식(Bottom-Up) 계산 방식이다.
재귀를 이용한 상향식 계산 예시 (꼬리 재귀 최적화 가능성)
public class FactorialTailRecursion {
public static int factorial2(int number) {
// 초기값 설정: 현재 곱할 숫자 i=1, 누적 합 sum=1
return factorial2(number, 1, 1);
}
private static int factorial2(int number, int i, int sum) {
if (i > number) { // 기저 조건: i가 number보다 커지면 누적된 sum 반환
return sum;
}
// 다음 호출: i를 1 증가시키고, sum에 i를 곱한 값을 넘김
return factorial2(number, i + 1, sum * i);
}
public static void main(String[] args) {
System.out.println(factorial2(5)); // 120
}
}
이 factorial2 함수는 재귀 함수지만, for문과 마찬가지로 작은 값부터 시작하여 큰 값으로 나아가며 결과를 누적하는 상향식 계산 방식을 따른다. 이런 형태의 재귀를 꼬리 재귀(Tail Recursion)라고 하며, 일부 컴파일러는 이를 반복문처럼 최적화하여 스택 오버플로우 위험을 줄이고 성능을 향상시킬 수 있다. 하지만 일반적인 재귀에서는 스택 오버헤드가 발생할 수 있다
재귀의 진정한 위력은 하향식 계산에 있다. 상향식 계산은 반복문으로 효율적으로 구현할 수 있으며, 재귀로 구현하더라도 대개 성능상 이점이 없다. 반면, 하향식 계산은 재귀가 특히 빛을 발하는 영역이다. 재귀를 사용하는 주된 이유는 바로 이 하향식으로 문제를 분해하고 해결하는 방식이 특정 유형의 문제를 더 직관적이고 간결하게 표현할 수 있기 때문이다.
하향식 재귀 예시: 배열의 모든 원소 합 구하기
배열의 모든 원소의 합을 구하는 문제를 하향식으로 풀어보자. 핵심은 하위 문제의 결과를 기반으로 현재 문제를 계산하는 것이다.
예를 들어,[1, 2, 3, 4, 5] 배열의 합을 구한다고 할 때, 하위 문제는 [1, 2, 3, 4] 배열의 합을 구하는 문제가 된다. 이 하위 문제의 결과에 마지막 원소 5만 더하면 현재 문제가 해결된다
public class ArraySumRecursionIndexed {
/*
* public 메서드는 외부에서 호출될 때 재귀 호출의 시작점을 제공한다.
* 실제 재귀 로직은 오버로드된 private 보조 함수 'sumArrayRecursive'에서 처리된다.
* 초기 호출 시, 배열의 마지막 인덱스부터 시작하도록 설정한다.
*/
public static int sumArray(int[] arr) {
// 배열이 비어있을 경우를 처리하는 추가적인 검사 (선택 사항)
if (arr == null || arr.length == 0) {
return 0;
}
return sumArrayRecursive(arr, arr.length - 1);
}
/*
* 보조 함수: 특정 인덱스까지의 합을 재귀적으로 계산한다.
* 하향식 사고 방식은 아니지만, 배열의 '끝'부터 시작하여 '시작'으로 거슬러 올라가며
* 각 원소를 처리하는 재귀적 접근 방식이다.
* (예: arr[index] + arr[index-1] + arr[index-2] ...)
*/
private static int sumArrayRecursive(int[] arr, int index) {
/*
* 기저 조건: 현재 인덱스가 0보다 작아지면 (즉, 모든 원소를 처리했거나 빈 배열인 경우),
* 더 이상 더할 원소가 없으므로 누적 합의 초기값인 0을 반환하여 재귀를 종료한다.
*/
if (index < 0) {
return 0;
}
/*
* 재귀 호출: 현재 인덱스의 원소(arr[index])에
* 그 이전 인덱스까지의 모든 원소의 합 (sumArrayRecursive(arr, index - 1))을 더한다.
* 이렇게 하위 문제 (이전 인덱스까지의 합)의 결과를 기반으로
* 현재 문제 (현재 인덱스까지의 합)를 계산한다.
*/
return arr[index] + sumArrayRecursive(arr, index - 1);
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int sum = sumArray(arr);
System.out.println(sum); // 15
}
}
초기 호출
symArray){1, 2, 3, 4, 5}) -> (내부적으로) sumArrayRecursive({1, 2, 3, 4, 5}, 4)
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=4) │
│ - if (4 < 0) 은 거짓 │
│ - return arr[4] + sumArrayRecursive(arr, 3) │ ← 현재 실행 중인 코드 라인
└───────────────────────────────────────────────┘
sumArrayRecursive가 index=4로 호출되어 콜 스택에 올라왔다. 기저 조건(4 < 0)은 거짓이다. arr[4] (값 5)에 sumArrayRecursive(arr, 3 (4 – 1))의 반환 값을 더하기 위해 지귀 호출을 한다
sumArrayRecursive(arr, 3)호출 시점
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=3) │
│ - if (3 < 0) 은 거짓 │
│ - return arr[3] + sumArrayRecursive(arr, 2) │ ← 현재 실행 중인 코드 라인
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=4) │
│ - 대기 중: 5 + (하위 함수 반환 값) │
└───────────────────────────────────────────────┘
index=3으로 호출된 함수가 index=4 함수 위에 콜 스택에 쌓인다. 기저 조건은 거짓이고, arr[3] (값 4)에 sumArrayRecursive(arr, 2)의 반환 값을 더하기 위해 재귀 호출한다. index=4 ㅎ마수는 이 반환 값을 기다린다.
sumArrayRecursive(arr, 2) 호출 시점
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=2) │
│ - if (2 < 0) 은 거짓 │
│ - return arr[2] + sumArrayRecursive(arr, 1) │ ← 현재 실행 중인 코드 라인
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=3) │
│ - 대기 중: 4 + (하위 함수 반환 값) │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=4) │
│ - 대기 중: 5 + (하위 함수 반환 값) │
└───────────────────────────────────────────────┘
index=2 함수가 index=3 함수 위에 쌓인다. arr[2] (값 3)에 sumArrayRecursive(arr, 1)의 반환 값을 더하기 위해 재귀 호출한다
sumArrayRecursive(arr, 1) 호출 시점
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=1) │
│ - if (1 < 0) 은 거짓 │
│ - return arr[1] + sumArrayRecursive(arr, 0) │ ← 현재 실행 중인 코드 라인
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=2) │
│ - 대기 중: 3 + (하위 함수 반환 값) │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=3) │
│ - 대기 중: 4 + (하위 함수 반환 값) │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=4) │
│ - 대기 중: 5 + (하위 함수 반환 값) │
└───────────────────────────────────────────────┘
index=1 함수가 index=2 함수 위애 쌓인다. arr[1] (값 2)에 sumArrayRecursive(arr, 0)의 반환 값을 더하기 위해 재귀 호출한다
sumArrayRecursive(arr, 0) 호출 시점
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=0) │
│ - if (0 < 0) 은 거짓 │
│ - return arr[0] + sumArrayRecursive(arr, -1) │ ← 현재 실행 중인 코드 라인
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=1) │
│ - 대기 중: 2 + (하위 함수 반환 값) │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=2) │
│ - 대기 중: 3 + (하위 함수 반환 값) │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=3) │
│ - 대기 중: 4 + (하위 함수 반환 값) │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=4) │
│ - 대기 중: 5 + (하위 함수 반환 값) │
└───────────────────────────────────────────────┘
index=0 함수가 index=1 함수 위에 쌓인다. arr[0] (값 1)에 sumArrayRecursive(arr, -1)의 반환 값을 더하기 위해 재귀 호출한다
sumArrayRecursive(arr, -1) 호출 시점 (기저 조건 달성)
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=-1) │
│ - if (-1 < 0) 은 참 │ ← 현재 실행 중인 코드 라인
│ - return 0 │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=0) │
│ - 대기 중: 1 + (하위 함수 반환 값) │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=1) │
│ - 대기 중: 2 + (하위 함수 반환 값) │
└───────────────────────────────────────────────┘
... (이하 생략)
index=1 함수가 index=0 함수 위에 쌓인다. 기저 조건 if (-1 < 0)이 참이 된다. 함수는 더 이상 재귀 호출 없이 즉이 0을 반환하고 종료된다
sumArrayRecursive(arr, -1) 종료 및 값 반환 (스택 해제 시작)
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=0) │
│ - 재개: 1 + (sumArrayRecursive(arr, -1)의 반환값)│ ← 현재 실행 중인 코드 라인
│ - 1 + 0 계산 │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=1) │
│ - 대기 중: 2 + (하위 함수 반환 값) │
└───────────────────────────────────────────────┘
... (이하 생략)
sumArrayRecursive(arr, -1)이 0을 반환하며 콜 스택에서 제거된다. 이제 sumArrayRecursive(arr, 0)이 실행을 재개한다. arr[0] (1)에 0을 더하고 1을 계산하고, 이 값을 반환한다
sumArrayRecursive(arr, 0) 종료 및 값 반환
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=1) │
│ - 재개: 2 + (sumArrayRecursive(arr, 0)의 반환값) │ ← 현재 실행 중인 코드 라인
│ - 2 + 1 계산 │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=2) │
│ - 대기 중: 3 + (하위 함수 반환 값) │
└───────────────────────────────────────────────┘
... (이하 생략)
sumArrayRecursive(arr, 0)이 1을 반환하며 콜 스택에서 제거된다 sumArrayRecursive(arr, 1)이 실행을 재개한다. arr[1] (2)에 1을 더하여 3을 계산하고, 이 값을 반환한다
sumArrayRecursive(arr, 1) 종료 및 값 반환
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=2) │
│ - 재개: 3 + (sumArrayRecursive(arr, 1)의 반환값) │ ← 현재 실행 중인 코드 라인
│ - 3 + 3 계산 │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=3) │
│ - 대기 중: 4 + (하위 함수 반환 값) │
└───────────────────────────────────────────────┘
... (이하 생략)
sumArrayRecursive(arr, 1)이 3을 반환하며 콜 스택에서 제거된다. sumArrayRecursive(arr, 2)가 실행을 재개한다. arr[2] (3)에 3을 더하여 6을 계산하고, 이 값을 반환한다
sumArrayRecursive(arr, 2) 종료 및 값 반환
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=3) │
│ - 재개: 4 + (sumArrayRecursive(arr, 2)의 반환값) │ ← 현재 실행 중인 코드 라인
│ - 4 + 6 계산 │
├───────────────────────────────────────────────┤
│ sumArrayRecursive(arr={1,2,3,4,5}, index=4) │
│ - 대기 중: 5 + (하위 함수 반환 값) │
└───────────────────────────────────────────────┘
sumArrayRecursive(arr, 2)이 6을 반환하며 콜 스택에서 제거된다. sumArrayRecursive(arr, 3)이 실행을 재개합니다. arr[3] (4)에 6을 더하여 10을 계산하고, 이 값을 반환한다.
sumArrayRecursive(arr, 3) 종료 및 값 반환
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=4) │
│ - 재개: 5 + (sumArrayRecursive(arr, 3)의 반환값) │ ← 현재 실행 중인 코드 라인
│ - 5 + 10 계산 │
└───────────────────────────────────────────────┘
sumArrayRecursive(arr, 2)이 6을 반환하며 콜 스택에서 제거된다. sumArrayRecursive(arr, 3)이 실행을 재개합니다. arr[3] (4)에 6을 더하여 10을 계산하고, 이 값을 반환한다.
sumArrayRecursive(arr, 3) 종료 및 값 반환
[콜 스택]
┌───────────────────────────────────────────────┐
│ sumArrayRecursive(arr={1,2,3,4,5}, index=4) │
│ - 재개: 5 + (sumArrayRecursive(arr, 3)의 반환값) │ ← 현재 실행 중인 코드 라인
│ - 5 + 10 계산 │
└───────────────────────────────────────────────┘
sumArrayRecursive(arr, 3)이 10을 반환하며 콜 스택에서 제거된다. sumArrayRecursive(arr, 4)가 실행을 재개합니다. arr[4] (5)에 10을 더하여 15를 계산하고, 이 값을 반환한다
sumArrayRecursive(arr, 4) 종료 및 최종 값 반환
[콜 스택] (빈 콜 스택)
sumArrayRecursive(arr, 4)이 15를 반환하며 콜 스택에서 제거된다. 모든 재귀 호출이 완료되고 최종 결과 15가 호출자(여기서는 main 메서드)에게 전달된다
하향식 재귀 예제: 문자열 길이 계산 – strLength()
하위 문제를 생각할 때, 구하려는 문자열의 마지막 원소(문자)를 제외한 나머지 부분의 길이가 하위 문제가 된다. 예를 들어 “abcd”라는 문자열의 길이를 구한다면, “abc”의 길이가 하위 문제이다. “abc”의 길이가 이미 해결되었다고 가정하고, 여기에 마지막 문자 “e”의 길이인 1을 더하면 전체 문자열의 길이를 얻을 수 있다
public class StringLengthRecursion {
/*
* 하위 문제의 결과를 기반으로 현재 문제를 계산한다.
* str.substring(0, str.length() - 1)는 문자열의 마지막 문자를 제외한 나머지 부분이다.
* 이 하위 문제의 길이에 +1 (마지막 문자의 길이)을 더해 현재 문제를 해결한다.
*
* 기저 조건: 문자열이 비어있을 때 (str.isEmpty()).
* 빈 문자열의 길이는 0이다.
*/
public static int strLength(String str) {
if (str == null || str.isEmpty()) { // 기저 조건: 문자열이 null이거나 비어있을 때
return 0;
}
// 하위 문자열 (마지막 문자 제외)의 길이 + 1
return strLength(str.substring(0, str.length() - 1)) + 1;
}
public static void main(String[] args) {
String str = "abcd";
int len = strLength(str);
System.out.println(len); // 4
}
}
초기 호출: strLength(“abcd”)
strLength(“abcd”) 호출 시점
[콜 스택]
┌───────────────────────────────────────┐
│ strLength("abcd") │
│ - if (str.isEmpty()) 는 거짓 │
│ - return strLength("abc") + 1 │ ← 현재 실행 중인 코드 라인
└───────────────────────────────────────┘
strLength(“abcd”가 콜 스택에 올라왔다. 문자열이 비어있지 않으므로, strLength(“abc”)를 호출하여 그 결과에 1을 더할 준비를 한다
strLength(“abc”) 호출 시점
[콜 스택]
┌───────────────────────────────────────┐
│ strLength("abc") │
│ - if (str.isEmpty()) 는 거짓 │
│ - return strLength("ab") + 1 │ ← 현재 실행 중인 코드 라인
├───────────────────────────────────────┤
│ strLength("abcd") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
└───────────────────────────────────────┘
strLength(“abc”)가 strLength(“abcd”) 위에 콜 스택에 쌓인다. strLength(“ab”)를 호출하여 그 결과에 1을 더할 준비를 한다. 이전 함수는 대기한다
strLength(“ab”) 호출 시점
[콜 스택]
┌───────────────────────────────────────┐
│ strLength("ab") │
│ - if (str.isEmpty()) 는 거짓 │
│ - return strLength("a") + 1 │ ← 현재 실행 중인 코드 라인
├───────────────────────────────────────┤
│ strLength("abc") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
├───────────────────────────────────────┤
│ strLength("abcd") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
└───────────────────────────────────────┘
strLength(“ab”)가 strLength(“abc”) 위에 쌓인다. strLength(“a”)를 호출한다
strLength(“a”) 호출 시점
[콜 스택]
┌───────────────────────────────────────┐
│ strLength("a") │
│ - if (str.isEmpty()) 는 거짓 │
│ - return strLength("") + 1 │ ← 현재 실행 중인 코드 라인
├───────────────────────────────────────┤
│ strLength("ab") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
├───────────────────────────────────────┤
│ strLength("abc") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
├───────────────────────────────────────┤
│ strLength("abcd") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
└───────────────────────────────────────┘
strLength(“a”)가 strLength(“ab”) 위에 쌓입니다. strLength(“”)를 호출한다
strLength(“”) 호출 시점 (기저 조건 달성)
[콜 스택]
┌───────────────────────────────────────────┐
│ strLength("") │
│ - if (str.isEmpty()) 는 참 │ ← 현재 실행 중인 코드 라인
│ - return 0 │
├───────────────────────────────────────────┤
│ strLength("a") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
├───────────────────────────────────────────┤
│ strLength("ab") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
└───────────────────────────────────────────┘
... (이하 생략)
strLength(“”)가 strLength(“a”) 위에 쌓인다. 기저 조건 if (str.isEmpty())가 참이 된다. 함수는 더 이상 재귀 호출 없이 즉시 0을 반환하고 종료된다
strLength(“”) 종료 및 값 반환 (스택 해제 시작)
[콜 스택]
┌───────────────────────────────────────────┐
│ strLength("a") │
│ - 재개: (strLength("")의 반환값) + 1 │ ← 현재 실행 중인 코드 라인
│ - 0 + 1 계산 │
├───────────────────────────────────────────┤
│ strLength("ab") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
└───────────────────────────────────────────┘
... (이하 생략)
strLength(“”)가 0을 반환하며 콜 스택에서 제거된다. strLength(“a”)가 실행을 재개합니다. 0 + 1을 계산하여 1을 반환한다
strLength(“a”) 종료 및 값 반환
[콜 스택]
┌───────────────────────────────────────────┐
│ strLength("ab") │
│ - 재개: (strLength("a")의 반환값) + 1 │ ← 현재 실행 중인 코드 라인
│ - 1 + 1 계산 │
├───────────────────────────────────────────┤
│ strLength("abc") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
└───────────────────────────────────────────┘
... (이하 생략)
strLength(“a”)가 1을 반환하며 콜 스택에서 제거된다. strLength(“ab”)가 실행을 재개한다. 1 + 1을 계산하여 2를 반환한다
strLength(“ab”) 종료 및 값 반환
[콜 스택]
┌───────────────────────────────────────────┐
│ strLength("abc") │
│ - 재개: (strLength("ab")의 반환값) + 1 │ ← 현재 실행 중인 코드 라인
│ - 2 + 1 계산 │
├───────────────────────────────────────────┤
│ strLength("abcd") │
│ - 대기 중: (하위 함수 반환 값) + 1 │
└───────────────────────────────────────────┘
... (이하 생략)
strLength(“ab”)가 2를 반환하며 콜 스택에서 제거된다. strLength(“abc”)가 실행을 재개한다. 2 + 1을 계산하여 3을 반환한다
strLength(“abc”) 종료 및 값 반환
[콜 스택]
┌───────────────────────────────────────────┐
│ strLength("abcd") │
│ - 재개: (strLength("abc")의 반환값) + 1 │ ← 현재 실행 중인 코드 라인
│ - 3 + 1 계산 │
└───────────────────────────────────────────┘
strLength(“abc”)가 3을 반환하며 콜 스택에서 제거된다. strLength(“abcd”)가 실행을 재개한다. 3 + 1을 계산하여 4를 반환한다
strLength(“abcd”) 종료 및 최종 값 반환
[콜 스택] (빈 콜 스택)
strLength(“abcd”)가 4를 반환하며 콜 스택에서 제거된다. 모든 재귀 호출이 완료되고 최종 결과 4가 호출자에게 전달된다
하향식 재귀 예제: 지수 함수 power(x, n)
마지막으로 지수 함수 x의 n승 (x^n)을 하향식으로 구현해 봅시다. 이는 밑 x를 지수 n만큼 곱하는 연산입니다. 예를 들어, 2의 4승은 2 * 2 * 2 * 2 이다.
하위 문제는 무엇일까? x의 n승에서 하위 문제는 x의(n-1)승이다. 만약 x의 (n-1)승의 값이 이미 계산되었다고 가정한다면, 여기에 x를 한 번 더 곱하면 x의 n승이 된다
public class PowerRecursion {
/*
* 하위 문제의 결과를 기반으로 현재 문제를 계산합니다.
* power(x, n - 1)는 x의 (n-1)승이라는 하위 문제입니다.
* 이 결과에 x를 곱하여 x의 n승을 계산합니다.
*
* 기저 조건: 지수 n이 0일 때 (n == 0).
* 수학적으로 어떤 수의 0승은 1입니다 (단, 0의 0승은 정의에 따라 다름. 여기서는 양의 x를 가정).
*/
public static int power(int x, int n) {
if (n == 0) { // 기저 조건
return 1;
}
return power(x, n - 1) * x; // 하위 문제 (power(x, n-1))의 결과에 x를 곱함
}
public static void main(String[] args) {
System.out.println(power(2, 4)); // 16
}
}
초기 호출: power(2, 4)
power(2, 4)호출 시점
[콜 스택] ┌───────────────────────────────────┐ │ power(x=2, n=4) │ │ - if (4 == 0) 는 거짓 │ │ - return power(2, 3) * 2 │ ← 현재 실행 중인 코드 라인 └───────────────────────────────────┘
power(2, 4)가 콜 스택에 올라왔다. n이 0이 아니므로, power(2, 3)를 호출하여 그 결과에 2를 곱할 준비를 한다.
power(2, 3)호출 시점
[콜 스택] ┌───────────────────────────────────┐ │ power(x=2, n=3) │ │ - if (3 == 0) 는 거짓 │ │ - return power(2, 2) * 2 │ ← 현재 실행 중인 코드 라인 ├───────────────────────────────────┤ │ power(x=2, n=4) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ └───────────────────────────────────┘
power(2, 3)이 power(2, 4) 위에 콜 스택에 쌓인다. power(2, 2)를 호출하여 그 결과에 2를 곱할 준비를 합니다. 이전 함수는 대기한다.
power(2, 2) 호출 시점
[콜 스택] ┌───────────────────────────────────┐ │ power(x=2, n=2) │ │ - if (2 == 0) 는 거짓 │ │ - return power(2, 1) * 2 │ ← 현재 실행 중인 코드 라인 ├───────────────────────────────────┤ │ power(x=2, n=3) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ ├───────────────────────────────────┤ │ power(x=2, n=4) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ └───────────────────────────────────┘
power(2, 2)가 power(2, 3) 위에 쌓인다. power(2, 1)을 호출한다.
power(2, 1) 호출 시점
[콜 스택] ┌───────────────────────────────────┐ │ power(x=2, n=1) │ │ - if (1 == 0) 는 거짓 │ │ - return power(2, 0) * 2 │ ← 현재 실행 중인 코드 라인 ├───────────────────────────────────┤ │ power(x=2, n=2) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ ├───────────────────────────────────┤ │ power(x=2, n=3) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ ├───────────────────────────────────┤ │ power(x=2, n=4) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ └───────────────────────────────────┘
power(2, 1)이 power(2, 2) 위에 쌓인다. power(2, 0)을 호출한다
power(2, 0) 호출 시점 (기저 조건 달성)
[콜 스택] ┌───────────────────────────────────────┐ │ power(x=2, n=0) │ │ - if (0 == 0) 는 참 │ ← 현재 실행 중인 코드 라인 │ - return 1 │ ├───────────────────────────────────────┤ │ power(x=2, n=1) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ ├───────────────────────────────────────┤ │ power(x=2, n=2) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ └───────────────────────────────────────┘ ... (이하 생략)
power(2, 0)이 power(2, 1) 위에 쌓인다. 기저 조건 if (0 == 0)이 참이 된다. 함수는 더 이상 재귀 호출 없이 즉시 1을 반환하고 종료된.
power(2, 0) 종료 및 값 반환 (스택 해제 시작)
[콜 스택] ┌───────────────────────────────────────┐ │ power(x=2, n=1) │ │ - 재개: (power(2, 0)의 반환값) * 2 │ ← 현재 실행 중인 코드 라인 │ - 1 * 2 계산 │ ├───────────────────────────────────────┤ │ power(x=2, n=2) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ └───────────────────────────────────────┘ ... (이하 생략)
power(2, 0)이 1을 반환하며 콜 스택에서 제거된다. power(2, 1)이 실행을 재개한다. 1 * 2를 계산하여 2를 반환한다
power(2, 1) 종료 및 값 반환
[콜 스택] ┌───────────────────────────────────────┐ │ power(x=2, n=2) │ │ - 재개: (power(2, 1)의 반환값) * 2 │ ← 현재 실행 중인 코드 라인 │ - 2 * 2 계산 │ ├───────────────────────────────────────┤ │ power(x=2, n=3) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ └───────────────────────────────────────┘ ... (이하 생략)
power(2, 1)이 2를 반환하며 콜 스택에서 제거된다. power(2, 2)가 실행을 재개한다. 2 * 2를 계산하여 4를 반환힌다
power(2, 2) 종료 및 값 반환
[콜 스택] ┌───────────────────────────────────────┐ │ power(x=2, n=3) │ │ - 재개: (power(2, 2)의 반환값) * 2 │ ← 현재 실행 중인 코드 라인 │ - 4 * 2 계산 │ ├───────────────────────────────────────┤ │ power(x=2, n=4) │ │ - 대기 중: (하위 함수 반환 값) * 2 │ └───────────────────────────────────────┘ ... (이하 생략)
power(2, 2)이 4를 반환하며 콜 스택에서 제거된다. power(2, 3)이 실행을 재개한다. 4 * 2를 계산하여 8을 반환한다
power(2, 3) 종료 및 값 반환
[콜 스택] ┌───────────────────────────────────────┐ │ power(x=2, n=4) │ │ - 재개: (power(2, 4)의 반환값) * 2 │ ← 현재 실행 중인 코드 라인 │ - 8 * 2 계산 │ └───────────────────────────────────────┘
power(2, 3)이 8을 반환하며 콜 스택에서 제거된다. power(2, 4)가 실행을 재개한다. 8 * 2를 계산하여 16을 반환한다
power(2, 4) 종료 및 최종 값 반환
[콜 스택] (빈 콜 스택)
power(2, 4)이 16를 반환하며 콜 스택에서 제거된다. 모든 재귀 호출이 완료되고 최종 결과 16가 호출자에게 전달된다.
재귀적 사고는 처음에는 익숙하지 않고 어렵게 느껴질 수 있다.(내 이야기??) 하지만 이처럼 다양한 예제를 통해 하위 문제의 정의, 기저 조건 설정, 그리고 하위 문제의 결과를 현재 문제에 어떻게 활용할지에 대해 꾸준히 고민하고 연습한다면, 점차 재귀를 활용하여 복잡한 문제들을 우아하고 효율적으로 해결할 수 있는 능력을 기를 수 있다. 계속해서 도전하고 탐구하는 자세가 중요하다.