해당 시리즈는 [Deep Dive] 스터디의 발표 내용으로, [모던 자바스크립트 Deep Dive]의 일부를 발췌하여 작성하였습니다.
모던 자바스크립트 Deep Dive 12.7.2 재귀함수 (p.182)
”재귀 함수는 반복되는 처리를 반복문 없이 구현할 수 있다는 장점이 있지만 무한 반복에 빠질 위험이 있고, 이로 인해 스택 오버플로 에러를 발생시킬 수 있으므로 주의해서 사용해야 한다. 따라서 재귀 함수는 반복문을 사용하는 것보다 재귀 함수를 사용하는 편이 더 직관적으로 이해하기 쉬울 때만 한정적으로 사용하는 것이 바람직하다.”
❓그렇다면 반복문과 재귀 함수 중 각자 어떤 식으로 더 성능이 좋은 걸까?
1. 재귀 함수와 반복문의 차이점
반복문과 재귀 함수의 성능 비교에 앞서, 둘의 차이점에 대해 알아보려고 한다.
가장 유명한 Factorial 구현 예시를 가지고 와보았다.
반복문을 통한 구현은 다음과 같다.
factorial 구현을 위해 매개변수 num을 받고 지역변수 result를 사용하였다.
function factorial(num) {
if (num <= 1) return 1
var result = num
while (--num) result *= num
return result
}
재귀 함수를 사용한 Factorial 구현은 어떠할까?
매개변수 num만을 사용하였다.
function factorial(num) {
if (num <= 1) return 1
return num * factorial(num - 1)
}
딱 보기에도 사용하는 변수의 개수나, 코드 길이가 다르다.
즉, 재귀를 사용하면 코드의 가독성이 더 좋아진다.
또한 복잡한 문제도 더 빠르고 단순하게 접근이 가능하다.
하지만 재귀 함수는 이렇듯 장점만 가지고 있을까?
모든 코드에는 장단점이 존재한다.
재귀 함수의 가장 큰 단점은 바로 Stack Overflow의 발생 우려이다.
2. 재귀 함수의 단점, Stack Overflow
재귀 함수는 본인을 다시 호출함으로써 Stack 메모리를 사용하는데, 반복적으로 자기 자신을 부르면서 Stack에 게속해서 쌓여간다.
만약 이게 점점 쌓여 Stack의 모든 공간을 차지하고 여유 공간이 없어진다면 Stack Overflow가 발생한다.
이에 비해서 반복문은 Stack 메모리에 1번만 쌓이게 된다.
📌 Stack Overflow는 '왜' 발생하는 것일까?
메모리 구조를 간단하게만 보았을 때,
Heap의 영역과 Stack의 영역이 차지하는 방향이 서로 맞물리는 구조를 가지고 있다.
Stack의 공간이 점점 커져서 Heap을 침범하는 경우에 StackOverflow가 발생하는 것이다.
3. 그럼에도 재귀 함수를 사용하는 이유는 무엇일까?
가장 큰 이유는 가독성과 직관적인 이해가 가능하다는 것이다.
협업이 필수인 요즘, 개발자가 지향해야 할 읽기 좋은 코드는 직관적인 코드이다.
복잡한 문제도 단순한 로직의 반복 구조로 해결하고,
함수 내에서 사용하는 변수의 개수와 코드 길이가 줄어들기에 읽기 좋은 코드가 될 수 있다.
또한 Stack Overflow가 발생하지 않도록 메모리 사용에 주의를 기울이는 방법을 사용한다면 재귀 함수의 단점을 보완할 수 있다.
여기서 나온 것이 바로 꼬리 재귀 기법이다.
4. 꼬리 재귀 기법?
자기 자신을 호출한 뒤 결과를 기다리면서 생기는 Stack의 부하로 인한 메모리 낭비를 줄여주기 위해 나온 기법이다.
먼저 일반 재귀 기법의 경우를 보자.
function sum(x) {
if(x === 100) return x;
else return x + sum(x + 1); // 문제 구간! return 된 후 연산이 일어난다.
}
sum(0)
함수를 return 하면서 sum(x+1)를 호출하고 결과를 기다린 뒤, x와 더하는 연산을 진행하고 있다.
함수를 return 하면서 기다리는 추가 연산이 있다.
즉, 함수가 return된 후 연산이 일어난다.
만약에 여기서 결과를 기다릴 필요가 없다면 어떠할까?
꼬리 재귀 기법의 경우를 살펴보자.
function tailSum(x, answer) {
if(x > 100) return answer;
else return tailSum(x + 1, answer + x) // return 되기 전에 연산을 한다.
}
tailSum(0, 0)
return 문에서 추가 연산을 없애고 바로 결과를 반환하도록 하였다.
둘의 차이점은 return 문에 있다.
일반 재귀의 경우 함수가 return 된 후에 연산이 일어나고,
꼬리 재귀의 경우 함수가 return 되기 전에 연산이 일어나는 것을 볼 수 있다.
즉 return문에서 재귀 호출 전에 문장이나 연산이 없어야 한다.
꼬리 재귀를 사용한다면 재귀 호출이 끝나는 시점에 아무 일도 하지 않고 바로 결과를 반환하도록 하는 방법으로
함수의 상태 유지 및 추가 연산을 하지 않기에 Stack Overflow를 해결할 수 있다.
하지만 이 또한 컴파일러가 꼬리 재귀 최적화를 지원한다는 가정하에 사용할 수 있다는 단점이 있다.
따라서 컴파일러가 자체적으로 재귀함수를 해석하여 반복문으로 변경하여 실행하는 '최적화 단계'를 지원해야 그 성능을 기대할 수 있다.
5. 결론
재귀 함수와 반복문의 사용은 시간 복잡도(메모리 사용)와 코드 크기에 따라 결정될 것 같다.
재귀 함수는 동일한 코드를 다시 호출하는 것이므로 코드 길이가 짧지만
그에 따른 시간 복잡도는 지수적으로 증가함으로 코드가 짧지만 시간 복잡도가 높은 경우에 유리할 것이다.
시간 복잡도(메모리 사용)의 문제보다는 코드의 단축이 문제인 경우 재귀를 사용하는 것이 좋을 것이며,
또한 재귀 깊이가 예측 가능한 경우에 사용하는 것이 안전할 것이다.
반면 반복문은 코드 블록의 반복이므로 코드의 길이가 크지만 시간 복잡도가 초점인 경우 사용하는 것이 좋다.