📌 요약
- 재귀함수 : 자기 자신을 호출하는 함수. '분할 정복' 방식
- 잘못된 재귀함수 → 스택 오버플로
- 재귀의 규칙
- 종료 조건
- 분할 정복
🔄 재귀(再歸, Recursion)란?
한자 그대로 해석하면 '다시 돌아오다'라는 뜻..
수학과 언어학, 예술에서 재귀는 '그 자신에 관해 정의한 것이 발생하는 것'을 나타낸다.
컴퓨터 과학 분야에서는 '재귀함수'로 사용되며,
재귀 함수는 '자기 자신을 호출하는 함수'이다.
재귀함수는 '분할 정복'방식을 통해 복잡한 문제를 해결한다.
재귀를 시작적으로 표현하면 아래와 같다.
⚙ 재귀의 규칙
재귀함수를 잘못 구현한다면..?
재귀함수를 잘못 구현한 경우 심각한 문제를 일으킬 수 있다.
일반적으로 함수는 호출될 때 메모리 스택stack 영역에 쌓이고(메모리를 할당하고),
값을 리턴한 후 할당된 메모리를 해제한다.
보통 재귀함수를 잘못 구현했을 경우 무한하게 재귀함수를 호출만(메모리를 할당만) 하게 된다.
메모리의 용량은 한계가 있으므로 언젠가 메모리의 스택 영역은 넘치게된다.
(사실 넘치는 상황이 되기 직전에 뻗어?버린다.. 일반적으로 '프로그램 충돌crash'로 표현하는 듯)
즉, 무한 재귀 호출은 스택 오버플로stack overflow를 일으킨다.
- 스택 오버플로stack overflow
프로그램의 콜 스택 최대 개수가 제한된 양의 주소 공간(메모리)을 초과할 때를 나타낸다.
아래 코드는 무한 재귀 호출의 예시다.
function func() {
return func();
}위 코드를 시각적으로 표현하면 네모가 무한하게 존재할 것이다..
가끔 엘리베이터를 타면 거울이 마주보며 부착된 곳을 본적 있을텐데,
한쪽을 보고있으면 거울 속 내가 무한하게 비쳐보인다.
나 자신이 함수이고, 거울이 호출한다고 생각했을 때, '내'가 무한히 거울에 호출된다.
딱 그 모양새다.
따라서 재귀함수를 올바르게 구현하기 위해서는 스택 오버플로를 피해야 하며,
스택 오버플로를 피하기 위한 특정 규칙이 존재한다. 해당 규칙은 다음과 같다.
규칙1. 종료 조건 (기저 조건)
재귀함수로 인한 스택 오버플로는 올바른 종료 조건을 갖추지 못한 결과일 가능성이 매우 크다.
function countDownToZero(n) {
// 종료 조건. 0에서 중단
if (n < 0) {
return; // 함수를 중단
} else {
console.log(n);
countDownToZero(n - 1); // 1만큼 감소
}
}
countDownToZero(12);규칙2. 분할 정복 방식
컴퓨터 과학 분야에서 '분할 정복 방식'은
'어떤 문제를 작은 단위로 나눠서 해당 작은 단위의 문제들을 모두 해결함으로써 문제를 해결하는 것'을 말한다.
위의 숫자 출력 코드에서, 1가 입력될 때의 문제는 2이 입력될 때의 문제의 부분 문제이다.
이런 식으로 문제는 '분할 정복'에 의해 점점 작아지면서 종료의 경우에 도달해야 한다.
개인적으로 for문으로 구현할 때 값을 대입해본다.
이럴 경우 보통 작은 경우의 수부터 시작하지 않는다.
머릿 속에서 for문 반복 횟수도 적고, 구현되었을 때에는 더 큰 수일 때를 가정하기 때문인 듯 하다.
하지만 재귀의 경우 작은 경우의 수부터 대입해보는 것이 좋은 것 같다.
경우의 수가 커질 수록 재귀를 반복하는 횟수가 많아지기 때문이다.
📚 참고 자료
- 배세민, 2019, 《자바스크립트로 하는 자료 구조와 알고리즘》, 에이콘출판
