1. 재귀
재귀는 풀이를 더 명확하게 만들어 준다.
재귀를 쓴다고 성능이 더 나아지지는 않는다.
사실 반복문이 더 성능이 좋은 경우가 많다.
이에 대해
스택 오버플로우에 있는 레이 케드웰의 말을 인용해보면
다음과 같이 이야기 할 수 있다.
" 프로그램에 반복문을 사용하면 프로그램의 성능을 향상시킬 수 있지만,
재귀를 사용하면 프로그래머의 능력을 향상시킬 수 있습니다.
상황에 따라 적절한 방법을 골라 사용하세요. "
대부분의 중요한 알고리즘들이 재귀를 사용하므로, 개념을 잘 이해하는 것이 중요하다.
2. 기본 단계와 재귀 단계
재귀 함수를 만들 때는
언제 재귀를 멈출지 알려줘야 한다.
그래서 모든 재귀 함수는
기본 단계 base case 와
재귀 단계 recursive case 라는
두 부분으로 나누어져 있다.
재귀 단계는
함수가 자기 자신을 호출하는 부분이다.
기본 단계는
함수가 자기 자신을 다시 호출하지 않는 경우,
즉 무한 반복으로 빠져들지 않게 하는 부분이다.
java 코드 예시
public class Recursive {
private void countdown(int i) {
System.out.println("[ i ]___________🚩 " + i );
// 기본 단계
if (i <= 1)
return;
// 재귀 단계
countdown(i - 1);
}
// 실행 확인
public static void main(String[] args) {
Recursive r = new Recursive();
r.countdown(4);
}
}실행 결과
[ i ]___________🚩 4
[ i ]___________🚩 3
[ i ]___________🚩 2
[ i ]___________🚩 1
종료 코드 0(으)로 완료된 프로세스3. 호출 스택
호출 스택은 프로그램에서 중요한 개념이다.
호출 스택은 일반적인 프로그래밍에서도 중요하지만,
재귀를 사용할 때 더욱 중요하다.
스택을 사용하면 편하지만,
모든 정보를 저장해야 하므로 메모리를 많이 소비한다.
함수 호출을 할 때마다 메모리를 사용한다.
스택이 너무 커질 경우
Exception java.lang.StackOverflowError
이런 에러를 만나게 된다.
StackOverFlow 에러를 피하기 위해서는
재귀 대신 반복문을 사용하거나,
꼬리 재귀라는 방법을 사용할 수 있다.
하지만 안타깝게도 자바 언어에서는 꼬리 재귀를 지원하지 않는다.
