프로그래밍의 핵심 개념 중 하나인 재귀 함수(Recursive Function)에 파고들어보자. 재귀는 단순히 어려운 개념이 아니라, 특정 유형의 문제를 우아하고 효율적으로 해결해준다.
재귀의 기본 개념: 자기 참조
재귀는 어떤 것을 정의할 때 자기 자신을 참조하는 것을 의미한다. 프로그래밍에서는 함수를 정의할 때 자기 자신을 다시 호출하는 방식을 사용하는데, 이렇게 재귀적으로 정의된 함수를 재귀 함수라고 한다
myFunction
public class RecursionExample {
public static void myFunction(int number) {
System.out.println(number);
myFunction(number + 1); // 자기 자신을 다시 호출
}
public static void main(String[] args) {
myFunction(1);
}
}
myFunction은 매개변수로 받은 number를 출력하고, number에 1을 더한 값을 새로운 매개변수로 하여 myFunction을 다시 호출한다. 이 코드를 실행하면 1부터 시작하여 숫자가 계속 증가하면서 출력되다가, 결국 프로그램이 비정상적으로 종료된다 (예를 들어, 12345와 같은 특정 숫자까지 출력될 수 있으며, 이는 시스템의 메모리 크기에 따라 다르다)
종료된 코드를 명시적으로 넣지 않았음에도 불구하고 프로그램이 멈췄다. 이는 함수 호출 정보를 저장하는 특별한 메모리 공간인 콜 스택(Call Stack)이 가득 찼기 때문이다. myFunction에는 함수 호출을 멈추는 기저 조건(Base Case), 즉 탈출 조건이 없으므로, 메모리가 허용하는 한 계속해서 자기 자신을 호출하다가 스택 오버플로우(Stack Overflow)가 발생하여 프로그램이 종료되는 것이다. 이처럼 기저 조건이 없는 재귀 함수를 실제로 활용될 수 없다
재귀 함수의 필수 요소: 기저 조건
재귀 함수가 올바르게 동작하기 위해서는 반드시 기저 조건이 필요하다. 기저 조건은 재귀 호출을 멈추고 함수가 값을 반환하도록 하는 특정 조건이다. 1부터 3까지 숫자를 출력하는 예제를 통해 기저 조건의 중요성을 이해해보자.
일반적인 for 루프를 사용하면 다음과 같이 간단하게 구현할 수 있다
for (int i = 1; i < 4; i++) {
System.out.println(i); // 1, 2, 3 출력
}
이제 이 로직을 재귀 함수로 구현해본다. 기존의 myFunction에 기저 조건을 추가하여 3까지만 출력하고 멈추도록 수정한다
public class RecursionExampleWithBaseCase {
public static void myFunction(int number) {
// 기저 조건: number가 3보다 크면 함수 종료
if (number > 3) {
return;
}
System.out.println(number);
myFunction(number + 1);
}
public static void main(String[] args) {
myFunction(1); // 1, 2, 3 출력 후 종료
}
}
number의 값이 3보다 크면 함수가 즉시 종료(return)하도록 조건을 추가했다. 이제 myFunction(1)을 호출하면 1, 2, 3을 출력한 뒤, myFunction(4)가 호출될 때 if (number > 3) 조건이 참이 되어 함수가 종료된다. 이로써 무한 재귀를 방지하고 원하는 시점에 함수를 종료할 수 있게 되었다.
재귀의 핵심: 콜 스택의 이해
재귀 함수를 깊이 이해하기 위해서는 콜 스택(Call Stack) 개념을 정확히 알아야 한다. 콜 스택은 함수 호출 정보를 저장하는 메모리 영역으로, 스택(Stack) 자료구조의 특성인 FILO(First-In, Last-Out), 즉 “먼저 들어온 데이터가 나중에 나간다”는 원칙을 따른다
함수가 호출되면 해당 함수의 스택 프레임(Stack Frame)에 콜 스택에 생성되어 쌓인다. 이 스택 프레임은 함수의 매개변수, 지역 변수와 같은 실행에 필요한 모든 정보를 포함하며, 함수 실행이 완료되면 콜 스택에서 제거된다
두 가지 상황을 통해 콜 스택의 동작을 살펴보자
상황1: 독립적인 함수 호출
public class StackExample1 {
public static int functionA() {
int a = 10;
int b = 5;
return a + b; // 15
}
public static int functionB() {
int a = 10;
int b = 5;
return a - b; // 5
}
public static void main(String[] args) {
functionA();
functionB();
}
}
- functionA()가 호출되면, functionA의 스택 프레임이 콜 스택에 올라간다
- functionA가 모두 실행되고, 반환 값이 계산되면 콜 스택에서 functionA가 제거된다
- functionB()가 호출되면, functionB의 스택 프레임이 콜 스택에 올라간다
- functionB가 모두 실행되고, 반환 값이 계산되면 콜 스택에서 functionB가 제거된다
상황2: 함수 내에서 다른 함수 호출
public class StackExample2 {
public static int functionA() {
int a = 10;
int b = 5;
int c = functionB(); // functionB 호출
return a + b + c; // 10 + 5 + 5 = 20
}
public static int functionB() {
int a = 10;
int b = 5;
return a - b; // 5
}
public static void main(String[] args) {
functionA();
}
}
- functionA()가 호출되면, functionA의 스택 프레임이 콜 스택에 올라간다
- functionA 내부에서 functionB()를 호출한다. 이때 functionA는 아직 종료되지 않은 상태이다
- functionA 위에 functionB의 스택 프레임이 콜 스택에 올라간다
- functionB가 모두 실행되고 반환 값(5)를 functionA로 넘겨준 뒤 콜 스택에서 functionB가 제거된다
- functionA는 functionB의 반환 값(5)을 받아 나머지 코드를 실행하고, 모든 실행이 완료되면 콜 스택에서 functionA가 제거된다
콜 스택은 스택 자료구조의 특성을 활용한 대표적인 사례이다
재귀 함수의 콜 스택 동작
아제 앞서 보았던 재귀 함수 myFunction이 콜 스택에서 어떻게 동작하는지 자세히 살펴보자
public class RecursionCallStack {
public static void myFunction(int number) {
if (number > 3) { // 기저 조건
return;
}
System.out.println(number);
myFunction(number + 1); // 재귀 호출
}
public static void main(String[] args) {
myFunction(1);
}
}
초기 호출: myFunction(1)
myFunction(1) 호출 시점
┌─────────────────┐ │ myFunction(1) │ (number = 1) │ - println(1) │ │ - myFunction(2) │ ← 현재 실행 중인 코드 라인 └─────────────────┘
myFunction(1)이 콜 스택에 올라왔다. number는 1이다. 기저 조건(1 > 3)은 거짓이므로 1을 출력하고 다음으로 myFunction(2)로 호출한다
myFunction(2) 호출 시점
┌─────────────────┐ │ myFunction(2) │ (number = 2) │ - println(2) │ │ - myFunction(3) │ ← 현재 실행 중인 코드 라인 ├─────────────────┤ │ myFunction(1) │ (number = 1) │ - println(1) │ │ - myFunction(2) │ (현재 대기 중) └─────────────────┘
myFunction(2)가 myFunction(1)위에 콜 스택에 올라왔다. number는 2이다. 기저 조건 (2 > 3)은 거짓이므로 2를 출력하고, 다음으로 myFunction(3)을 호출한다. myFunction(1)은 myFunction(2)의 완료를 기다리며 일지 정시 상태이다.
myFunction(3) 호출 시점
┌─────────────────┐ │ myFunction(3) │ (number = 3) │ - println(3) │ │ - myFunction(4) │ ← 현재 실행 중인 코드 라인 ├─────────────────┤ │ myFunction(2) │ (number = 2) │ - println(2) │ │ - myFunction(3) │ (현재 대기 중) ├─────────────────┤ │ myFunction(1) │ (number = 1) │ - println(1) │ │ - myFunction(2) │ (현재 대기 중) └─────────────────┘
myFunction(3)이 myFunction(2) 위에 콜 스택에 올라왔다. number는 3이다. 기저 조건 (3 > 3)은 거짓이므로 3을 출력하고, 다음으로 myFunction(4)를 호출한다. 이전 함수들은 계속 대기중이다
myFunction(4) 호출 시점 (기저 조건 달성)
┌─────────────────┐ │ myFunction(4) │ (number = 4) │ - if (4 > 3) │ ← 현재 실행 중인 코드 라인 │ - return │ ├─────────────────┤ │ myFunction(3) │ (number = 3) │ - println(3) │ │ - myFunction(4) │ (현재 대기 중) ├─────────────────┤ │ myFunction(2) │ (number = 2) │ - println(2) │ │ - myFunction(3) │ (현재 대기 중) ├─────────────────┤ │ myFunction(1) │ (number = 1) │ - println(1) │ │ - myFunction(2) │ (현재 대기 중) └─────────────────┘
myFunction(4)가 myFunction(3) 위에 콜 스택에 올라왔다. number는 4이다. 기저 조건 if (4 > 3)이 참이 된다. return 문이 실행되어 myFunction(4)는 더 이상 코드를 실행하지 않고 즉시 종료된다
myFunction(4) 종료 및 스택에서 제거
┌─────────────────┐ │ myFunction(3) │ (number = 3) │ - println(3) │ │ - myFunction(4) │ (이전 호출 완료) ← 현재 실행 중인 코드 라인 │ - (코드 없음) │ ├─────────────────┤ │ myFunction(2) │ (number = 2) │ - println(2) │ │ - myFunction(3) │ (현재 대기 중) ├─────────────────┤ │ myFunction(1) │ (number = 1) │ - println(1) │ │ - myFunction(2) │ (현재 대기 중) └─────────────────┘
myFunction(4)가 종료되면서 콜 스택에서 제거된다. myFunction(3)의 실행이 재개된다. myFunction(3)은 myFunction(4) 호출 다음 코드가 없으므로, 더 이상 실행할 코드가 없다. 따라서 myFunction(3)도 종료된다.
myFunction(3) 종료 및 스택에서 제거
┌─────────────────┐ │ myFunction(2) │ (number = 2) │ - println(2) │ │ - myFunction(3) │ (이전 호출 완료) ← 현재 실행 중인 코드 라인 │ - (코드 없음) │ ├─────────────────┤ │ myFunction(1) │ (number = 1) │ - println(1) │ │ - myFunction(2) │ (현재 대기 중) └─────────────────┘
myFunction(3)이 종료되면서 콜 스택에서 제거된다. myFunction(2)의 실행이 재개되지만, 더 이상 실행할 코드가 없으므로 myFunction(2)도 종료된다
myFunction(2)종료 및 스택에서 제거
┌─────────────────┐ │ myFunction(1) │ (number = 1) │ - println(1) │ │ - myFunction(2) │ (이전 호출 완료) ← 현재 실행 중인 코드 라인 │ - (코드 없음) │ └─────────────────┘
myFunction(2)가 종료되면서 콜 스택에서 제거된다. myFunction(1)의 실행이 재개되지만, 더 이상 실행할 코드가 없으므로 myFunction(1)도 종료된다
myFunction(1) 종료 및 스택에서 제거
(빈 콜 스택)
myFunction(1)이 종료되면서 콜 스택에서 제거된다. 콜 스택이 비어졌으므로 모든 함수 호출이 완료되고 프로그램이 종료된다
이처럼 재귀 함수는 호출될 때마다 콜 스택에 새로운 함수 호출 스택 프레임에 쌓는다. 기저 조건이 없으면 콜 스택이 계속 쌓여 메모리 부족으로 인한 스택 오버플로우가 발생하게 된다. 이 때문에 단순히 반복적인 작업을 수행할 때는 for 루프와 같은 반복문이 재귀 함수보다 메모리 효율적인 경우가 많다. 재귀 함수는 반복문으로 해결하기 어려운 복잡한 문제를 더 직관적이고 우아하게 해결할 때 그 진가를 발휘한다
재귀 함수의 실용적인 활용: 팩토리얼
재귀 함수가 복잡한 문제를 쉽게 해결하는 대표적인 예시는 팩토리얼(Factorial) 계산이다. 수학에서 팩토리얼은 주어진 양의 정수 n에 대해 1부터 n까지의 모든 정수를 곱한 값이다. 예를 들어, 5! (5팩토리얼)은 5 * 4 * 3 * 2 * 1 = 120이다
팩토리얼을 재귀 함수로 구현해보자
public class FactorialRecursion {
/*
* 팩토리얼 함수는 n! = n * (n-1)! 이라는 점을 활용한다
* 예를 들어, 5! = 5 * 4! 이다
* 재귀 함수를 작성할 때는 '이미 이 함수가 구현되어 있다'고 가정하는 것이 도움이 된다
* factorial(number)는 number * factorial(number - 1)으로 정의할 수 있다
*
* 기저 조건: 팩토리얼은 1까지 곱하며, 0!은 1로 정의된다.
* 따라서 number가 0 또는 1일 때 1을 반환하도록 한다.
*/
public static int factorial(int number) {
if (number <= 1) { // 기저 조건
return 1;
} else {
return number * factorial(number - 1); // 재귀 호출
}
}
public static void main(String[] args) {
System.out.println(factorial(5)); // 120 출력
}
}
팩토리얼 재귀 함수의 동작 흐름
- factorial(5) 호출: 5 * factorial(4)
- factorial(4) 호출: 4 * factorial(3)
- factorial(3) 호출: 3 * factorial(2)
- factorial(2) 호출: 2 * factorial(1)
- factorial(1) 호출: number가 1이므로 기저 조건에 따라 1을 반환하고 종료된다
이제 역순으로 계산이 완료된다
- factorial(2)는 2 * 1 = 2를 반환
- factorial(3)는 3 * 2 = 6을 반환
- factorial(4)는 4 * 6 = 24를 반환
- factorial(5)는 5 * 24 = 120을 반환
이렇게 재귀 함수를 사용하면 팩토리얼과 같은 자기 자신을 포함하는 정의를 가진 문제를 매우 직관적이고 간결하게 표현할 수 있다
재귀 함수는 처음 접할 때는 혼란을 줄 수 있는 개념이다. 하지만 콜 스택의 동작을 직접 그려보면서 함수의 실행 흐름을 천천히 따라가다 보면 점차 이해의 깊이를 더할 수 있을 것이다. (라고 하지만 어렵다. 역시 공부다)