재귀 알고리즘
재귀란?
어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 합니다.
재귀함수를 이용하는 대표적인 알고리즘
- 팩토리얼
|
public class Factorial {
static int factorial(int n) {
if(n>0)
return n*factorial(n-1);
else
return 1;
}
}
|
cs |
- 유클리드 호제법
|
public class EuclidGCD {
static int gcd(int x, int y) {
if(y==0)
return x;
else
return gcd(y,x%y);
}
}
|
cs |
- 하노이의 탑
|
public class Hanoi {
// no개의 원반을 x번 기둥에서 y번 기둥으로 옮김
static void move(int no, int x, int y) {
if(no>1)
move(no-1, x , 6-x-y);
System.out.println("원반"+no+"을 "+x+"기둥에서 "+y+"기둥으로 옮김");
if(no>1)
move(no-1, 6-x-y, y);
}
}
|
cs |
바람직한 에
- 병합정렬, 퀵 정렬
- 팩토리얼 구하기
- 그래프의 DFS
- dp (큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함될 때)
치명적인 예
- 피보나치 수 구하기
- 행렬곱셈 최적순서 구하기
- dp (재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생)
재귀함수의 특징
왜 재귀를 사용하는가? (장점)
- 재귀 알고리즘을 사용한 코드는 훨씬 간결하고 오류 수정이 용이하다.
단점
- 코드를 이해하기 어렵게 만들고 기억 공간을 많이 요구한다.
문제점
- 자신을 다시 호출하면서 생성되는 변수는 새롭게 생성된 변수들이다. 곧, 메모리 문제를 야기시킬수도 있다.
- 속도 저하의 문제가 있지만 문제를 상쇄할 간결함과 편리함으로 재귀함수의 유용성은 뛰어나다.
- 재귀 호출은 내부적으로 스택 메모리를 통해 수행된다. 함수는 활성 레코드에 관련 정보를 정하는데, 이 활성 레코드들이 스택 메모리에 순서대로 저장된 뒤 차례로 Pop되어 처리된다. 이 과정에서 context switching 이 일어나서 재귀 호출은 반복 호출에 비해 수행시간이 더 느려지다.
재귀 함수의 초기화
- 재귀함수를 사용할 때 가장 많이 하는 실수 중에 하나가 재귀함수 안에서의 초기화이다. 초기화를 하지 않으면 시스템이 무한 루프의 재귀함수를 돌아서, 메모리 오류를 범하게 된다.
- 재귀함수에서의 초기화란 재귀함수를 끝내는 반환점을 제공한다. 그러므로 재귀함수 안에서의 초기화는 반드시 필요하며 사용하지 않으면 끝나는 지점을 찾을 수 없으므로 무한 루프에 빠지게 된다.
출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 [시바타 보요, 옮긴이 : 강민 (이지스퍼블리싱)]