[알고리즘] 재귀(Recursion)

재귀란?

재귀는 자기 자신을 호출하는 프로그래밍 기법입니다. 큰 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘이라 할 수 있습니다.

재귀 함수는 호출될 때 스택 구조를 사용합니다.

각 함수 호출로 인해 콜 스택에 쌓이고, 함수가 종료되면 제거됩니다.

---

재귀의 기본 구조

재귀 함수가 자기 자신을 무한히 호출하면 콜 스택이 계속 쌓이게 됩니다. 결국에는 멈추는 지점이 필요합니다. 이 지점을 기저 조건(Base Case)라 부릅니다.

재귀 함수를 구성하는 데 필수적인 구성 요소는 다음과 같습니다.

 

• 기저 조건(Base Case):
  • 재귀 호출을 멈추는 조건입니다.
    기저 조건을 명확히 정의하지 않으면 무한 루프에 빠질 수 있습니다.
• 재귀 호출(Recursive Call):
  • 자기 자신을 다시 호출하는 부분입니다.

아래는 재귀 함수의 간단한 예시입니다.

#include <iostream>
using namespace std;

void func(int n) {
	//기저 조건
	if (n >= 5) {
		cout << n << " ";
		return;
	}
	//함수를 실행하면서 처리 되는 코드
	cout << n << " ";

	//재귀 호출
	func(n + 1);

	//다시 돌아오면서 실행되는 코드
	cout << n << " ";
} 

int main() {
	func(0);
	return 0;
}

 

결과

종료 조건을 만나기 전까지 재귀를 호출하다 5에서 멈추게 됩니다. 스택에 쌓이다 보니 func(0)이 가장 마지막에 반환되는 모습을 볼 수 있습니다.

 

---

이번엔 약간 더 복잡한 예시를 들어보겠습니다.

피보나치 수열을 재귀를 통해 구현해보겠습니다.

피보나치 수열(Fibonacci Sequence)은 다음과 같은 규칙을 따릅니다:

• 첫 번째 수: 0
• 두 번째 수: 1
• 세 번째부터: 이전 두 항의 합

수열 예시: 0, 1, 1, 2, 3, 5, 8, ...

#include <iostream>
using namespace std;

int fibonacci(int n) {
    // 기저 조건
    if (n == 0) return 0;
    if (n == 1) return 1;

    // 재귀 호출
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    cout << "피보나치 수열에서 원하는 항의 번호를 입력하세요: ";
    cin >> n;

    cout << "피보나치 수열의 " << n << "번째 항은 " << fibonacci(n) << "입니다." << endl;

    return 0;
}

fibonacci(5) 호출 시

1. fibonacci(5) → fibonacci(4) + fibonacci(3)
2. fibonacci(4) → fibonacci(3) + fibonacci(2)
3. fibonacci(3) → fibonacci(2) + fibonacci(1)
4. ...
5. 기저 조건(fibonacci(1) 또는 fibonacci(0))에 도달 후 결과 반환합니다.

이렇게 재귀를 통해 피보나치 수열을 구현한 것은 O(2^n)으로 사실 반복문으로 구현한 O(n)보다 훨씬 느립니다. 이는 중복 호출 때문인데, DP를 사용해 중복 계산을 제거해 성능을 개선시킬 수 있습니다.

 

아래는 DP를 통해 성능을 개선시킨 방법입니다.

#include <iostream>
using namespace std;

#define MAX 100
int dp[MAX] = {0}; // 계산 결과를 저장하는 배열

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    // 이미 계산된 값이 있으면 반환
    if (dp[n] != 0) return memo[n];

    // 계산된 값을 저장하고 반환
    dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return dp[n];
}

int main() {
    int n;
    cout << "피보나치 수열에서 원하는 항의 번호를 입력하세요: ";
    cin >> n;

    cout << "피보나치 수열의 " << n << "번째 항은 " << fibonacci(n) << "입니다." << endl;

    return 0;
}

 

이렇듯 재귀는 성능 문제를 고려해야 합니다. 또한 콜스택을 사용하다 보니 너무 깊은 재귀는 메모리 초과를 유발할 수 있습니다.

---

정리

재귀는 반복문보다 느리고, 메모리도 많이드는 단점이 있습니다. 그럼에도 재귀를 사용하는 이유는 코드를 간결하고 직관적으로 만드는데 도움이 되기 때문입니다. 예를들어 DFS 같은 알고리즘은 스택을 사용하기 때문에, 콜스택을 사용하는 재귀를 활용해 구현한다면 별도의 스택을 관리하지 않고 DFS를 쉽게 구현할 수 있습니다. 또한, 반복문을 사용하는 것보다 훨씬 코드가 간결합니다. 

 

---

관련 문제

https://www.acmicpc.net/problem/25501

https://www.acmicpc.net/problem/1991

https://www.acmicpc.net/problem/2447