알고리즘을 공부하는중에 재귀함수를 자주 쓰는것같다. 막연하게 DFS 문제 풀때에는 쓸줄만 알았는데 완전탐색 문제를 풀어보려하니 막히는것이다. 내가 재귀함수에 대해서 공부를 안했던 탓인거같아 공부를 해보았다 !
아무래도 여러 알고리즘을 보며 학습하는게 좋을거같아 여러 문제를 준비했다 !
재귀는 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 간단히 말해, 함수가 자기 자신을 호출하면서 문제를 점진적으로 해결해 나가는 방식이다. 재귀 함수는 복잡한 문제를 작은 단위로 나눠서 처리할 수 있는 강력한 도구이지만, 잘못 사용하면 스택 오버플로 오류가 발생할 수 있어 주의해야 한다.
이 글에서는 자바로 재귀 함수를 작성하는 방법과 함께 재귀 함수의 기본 원리, 예제 코드를 통해 어떻게 재귀를 사용하는지 자세히 알아보겠다 !
1. 재귀 함수란?
재귀 함수는 자기 자신을 호출하는 함수를 의미한다. 이를 통해 복잡한 문제를 작은 단위로 쪼개어 해결할 수 있다. 보통 재귀는 기저 조건과 재귀 조건으로 구성된다.
- 기저 조건: 재귀 호출이 멈추는 조건이다. 기저 조건이 없으면 함수가 무한히 호출되며 스택 오버플로 오류가 발생하게 된다.
- 재귀 조건: 기저 조건을 만나기 전까지 계속 자기 자신을 호출하여 문제를 해결하는 과정이다.
2. 재귀 함수의 기본 구조
재귀 함수의 기본 구조는 다음과 같다 !
public class RecursionExample {
// 재귀 함수 정의
public static void recursiveMethod(int n) {
// 기저 조건: n이 0이 되면 종료
if (n == 0) {
System.out.println("재귀 종료");
return;
}
// 재귀 호출
System.out.println("현재 n: " + n);
recursiveMethod(n - 1);
}
public static void main(String[] args) {
recursiveMethod(5); // 재귀 함수 호출
}
}
위 코드에서 recursiveMethod(5)가 호출되면 n이 5부터 시작하여 0이 될 때까지 계속 감소하면서 함수를 호출한다. n이 0이 되면 함수가 종료되면서 재귀 호출이 멈추게 된다.
출력 결과
현재 n: 5
현재 n: 4
현재 n: 3
현재 n: 2
현재 n: 1
재귀 종료이제 재귀 함수의 기본 구조를 알아보았으니 여러 예제를 보며 학습해보자 !!
이런건 반복해서 학습해줘야 빨리빨리 습득 할것만 같다 !!!!!!!!!
3. 재귀 함수의 대표적인 예제
예제 1: 팩토리얼 계산
팩토리얼은 주어진 정수 n에 대해 n * (n-1) * (n-2) * ... * 1을 계산하는 연산이다. 재귀를 이용한 팩토리얼 함수는 다음과 같이 작성할 수 있다.
public class Factorial {
// 재귀를 사용한 팩토리얼 함수
public static int factorial(int n) {
// 기저 조건: n이 0 또는 1일 때는 1을 반환
if (n == 0 || n == 1) {
return 1;
}
// 재귀 조건: n * (n-1) 팩토리얼
return n * factorial(n - 1);
}
public static void main(String[] args) {
int result = factorial(5); // 5! = 120
System.out.println("5! = " + result);
}
}출력 결과
5! = 120- 설명:
factorial(5)가 호출되면,5 * factorial(4)가 호출되고,factorial(4)는 다시4 * factorial(3)을 호출하는 방식으로 계속 이어진다.n이 1이 되면factorial(1)은 1을 반환하고, 최종적으로5 * 4 * 3 * 2 * 1 = 120이 된다.
예제 2: 피보나치 수열
피보나치 수열은 다음과 같은 수열이다. 0, 1, 1, 2, 3, 5, 8, 13, ... 각 항은 이전 두 항의 합으로 이루어져 있다. 재귀를 이용한 피보나치 수열 함수는 다음과 같이 작성할 수 있다 !
public class Fibonacci {
// 재귀를 사용한 피보나치 함수
public static int fibonacci(int n) {
// 기저 조건: n이 0 또는 1일 때는 n을 반환
if (n == 0 || n == 1) {
return n;
}
// 재귀 조건: (n-1)번째와 (n-2)번째의 피보나치 수 합
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {
int n = 10; // 피보나치 수열의 10번째 값 구하기
for (int i = 0; i <= n; i++) {
System.out.print(fibonacci(i) + " ");
}
}
}출력 결과
0 1 1 2 3 5 8 13 21 34 55- 설명:
fibonacci(10)이 호출되면fibonacci(9) + fibonacci(8)을 계산하고, 각각fibonacci(9)는 다시fibonacci(8) + fibonacci(7)을 호출하는 방식으로 이어진다. 이때, 기저 조건인n == 0또는n == 1을 만나면 값을 반환하고 재귀 호출이 종료된다.
예제 3: 하노이의 탑
재귀함수에 대한 강의를 들으며 하노이의 탑이라는 걸 처음 들어봤다. 강의에서 하노이의 탑을 예시로 들어 설명해주시는데 집중해서 들어도 두번만에 살~짝 이해했다 !
하노이의 탑 문제는 세 개의 막대와 여러 개의 원반을 사용하여 원반을 한 막대에서 다른 막대로 이동시키는 문제다. 재귀를 통해 문제를 해결할 수 있다.
public class HanoiTower {
// 재귀를 사용한 하노이의 탑 함수
public static void hanoi(int n, char from, char to, char aux) {
// 기저 조건: 원반이 1개일 때, 원반을 from에서 to로 이동
if (n == 1) {
System.out.println("원반 1을 " + from + "에서 " + to + "로 이동");
return;
}
// 재귀 조건: n-1개의 원반을 보조 막대(aux)로 이동
hanoi(n - 1, from, aux, to);
System.out.println("원반 " + n + "을 " + from + "에서 " + to + "로 이동");
// 보조 막대에 있는 n-1개의 원반을 목표 막대(to)로 이동
hanoi(n - 1, aux, to, from);
}
public static void main(String[] args) {
int numDisks = 3; // 원반 3개 사용
hanoi(numDisks, 'A', 'C', 'B'); // A에서 C로 이동 (B는 보조 막대)
}
}출력 결과
원반 1을 A에서 C로 이동
원반 2를 A에서 B로 이동
원반 1을 C에서 B로 이동
원반 3을 A에서 C로 이동
원반 1을 B에서 A로 이동
원반 2를 B에서 C로 이동
원반 1을 A에서 C로 이동- 설명:
hanoi(3, 'A', 'C', 'B')가 호출되면, 먼저hanoi(2, 'A', 'B', 'C')가 호출되고, 이후hanoi(1, 'A', 'C', 'B')까지 이어진다. 이러한 방식으로 문제를 작은 단위로 나누어 해결해나가며 최종적으로 모든 원반이 A에서 C로 이동하게 된다.
4. 재귀 함수의 장단점
장점:
- 코드 가독성이 좋아진다. 복잡한 문제를 간결하게 표현할 수 있다.
- 분할 정복, 백트래킹 등의 알고리즘을 쉽게 구현할 수 있다.
단점:
- 스택 오버플로 위험이 있다. 재귀 호출이 너무 깊어질 경우 스택 메모리가 초과되어 오류가 발생할 수 있다.
- 비효율성이 있을 수 있다. 특히 피보나치 수열과 같은 중복 계산이 발생하는 경우, 재귀 대신 반복문으로 처리하는 것이 효율적이다.
5. 언제 재귀를 사용할까?
재귀는 복잡한 문제를 단계적으로 해결하거나, 특정 문제를 반복적으로 분할하여 해결할 때 유용하다. 다음과 같은 경우에 사용하기 적합하다.
- 문제의 정의가 재귀적일 때: 예를 들어, 팩토리얼, 피보나치 수열, 하노이의 탑과 같은 문제는 재귀적으로 정의할 수 있기 때문에 재귀를 사용하는 것이 자연스럽다.
- 트리나 그래프 탐색을 수행할 때: 깊이 우선 탐색과 같은 알고리즘은 재귀를 이용하여 구현하기에 적합하다. 노드나 경로를 탐색할 때 재귀를 사용하면 코드가 간결해지고 이해하기 쉬워진다.
- 백트래킹을 사용한 문제 해결: 예를 들어, 미로 찾기, N-Queens 문제 등에서 재귀를 사용하여 조건을 만족하는 해를 찾아 나가는 것이 효과적이다.
6. 재귀 함수 사용 시 주의할 점
- 기저 조건 설정: 모든 재귀 함수에는 반드시 기저 조건이 필요하다. 기저 조건이 없으면 재귀가 무한히 반복되어 스택 오버플로 오류를 일으킨다.
- 재귀 깊이 제한: 자바에서는 기본적으로 재귀 깊이에 제한이 있기 때문에(일반적으로 1,000) 너무 깊은 재귀는 피해야 한다. 필요할 경우
StackOverflowError예외를 방지하기 위해 반복문으로 변경하거나,Xss옵션을 사용하여 스택 크기를 조정할 수 있다. - 재귀 함수의 효율성: 재귀가 중복된 연산을 많이 수행하는 경우 성능이 떨어질 수 있다. 이 경우 메모이제이션 기법을 사용하거나 반복문을 사용하여 문제를 해결해야 한다.
재귀 함수는 직관적이고 간결한 코드 작성을 가능하게 해주는 강력한 도구이다. 그러나 잘못 사용하면 성능 저하나 스택 오버플로와 같은 문제를 일으킬 수 있으므로 주의가 필요하다. 재귀를 사용할 때는 문제의 정의와 기저 조건, 그리고 메모리 효율성을 고려하여 적절하게 사용해야 한다 !! 포스팅한 예제 말고도 더 많은 예제들을 풀어보며 재귀 함수를 익혀야겠다 !!
