자신을 반복하는 재귀함수
재귀(再歸, Recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다.
또는 구조는 동일하지만 더 작은 경우를 해결하여 문제 전체를 해결하는 방법을 재귀라 한다. 반복문을 사용하는 코드는 항상 재귀 함수를 통해 구현하는 것이 가능하며, 그 반대도 가능하다.
그렇다면 그냥 반복문을 쓰면 되잖아?
어떤 측면에서는 물론 맞는 말이다. 이는 재귀함수가 가지고 있는 단점에서도 기인하는데 재귀함수는 다음과 같은 단점이 있다.
- 재귀의 깊이가 깊어 졌을 때, 함수를 반복적으로 호출하면서 스택 메모리에 콜 스택을 쌓게 된다. 콜 스택이 스택 메모리를 초과할 정도로 깊은 재귀라면 stack overflow가 발생하게 된다.
- 함수가 호출되고 종료될 때 스택 프레임을 구성하고 해체하는 과정에서 반복문보다 오버헤드가 든다. 따라서 반복문 보다 속도가 느리다.
하지만 그럼에도 재귀함수가 가지는 명확한 장점 때문에 재귀함수를 활용할줄 알아야 한다. 재귀함수는 다음과 같은 장점이 있다.
- 알고리즘을 기술한 그대로 코드로 표현된다. 즉 가독성이 높아지면서 유지보수가 쉬워지고 코드를 직관적으로 이해할 수 있다.
- 재귀 호출은 변수 사용을(특히 local scope 변수를)줄여줄 수 있다. 결과적으로 프로그램에 오류가 생길(잘못된 state로 전이할)가능성이 줄어든다. 또한 이 때문에 프로그램이 올바르게 작동하는 것을 확인 하기가 용이해 진다.
특히나 대부분의 프로그래밍 언어가 꼬리 재귀의 최적화를 지원하는 이상, 자원을 많이 필요로 한다는 단점 또한 회피할 수 있기 때문에 재귀 함수를 써야할 이유는 더욱 극명해 진다.
꼬리 재귀(Tail Call Recursion)
꼬리 재귀는 재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태
재귀함수의 예로써 많이 쓰이는 팩토리얼(계승)연산을 봐보자 일반적인 재귀함수는 다음과 같은 형태를 지닌다.
function fatorial(n) {
if(n === 1) {
return 1;
}
return n * factorial(n - 1);
}위와 같은 형태에서 재귀 함수는 다음과 같이 동작한다.
일반적인 재귀 함수는 n이 1에 이르러 리턴될때 까지 종료되지 않고 계속 깊어진다. 함수가 종료 되지 않기 때문에 콜 스택이 스택 메모리에 쌓이게 된다.
꼬리재귀는 다음과 같은 형태를 가진다.
function factorialTail(n, acc) {
if(n === 1) {
return acc;
}
return factorialTail(n - 1, acc * n);
}
function factorial(n) {
return factorialTail(n, 1);
}꼬리 재귀는 다음과 같이 작동한다.
일반적인 재귀 함수와 꼬리 재귀 함수의 가장 큰 차이는 재귀 함수의 리턴에 연산이 있는가? 이다. 재귀 함수는 리턴에 연산이 존재하여 명확한 리턴 값을 받고 돌아오기 전까지 함수가 종료되지 않지만 꼬리 재귀 함수는 리턴에 연산이 존재하지 않기 때문에 해당 함수가 종료된다.
재귀 함수에 대한 주의깊은 사용
이처럼 컴파일러가 꼬리 재귀 최적화를 지원한다면 재귀의 성능 문제도 해결할 수 있으며, 하드웨어의 발전으로 소프트웨어 자체 성능에 대한 중요성도 낮아지고 있는 상황에서 (협업 상황에서의) 코드의 가독성이 높아지고 코드에 오류 가능성을 줄여주는 재귀 함수의 사용은 바람직해 보인다.
그럼에도 재귀 함수의 stack overflow를 무시할 순 없기 떄문에 재귀의 깊이를 예측 가능한 경우를 위주로 사용해야 현명하게 재귀 함수를 활용하는 것이라 할 수 있다.
재귀적으로 사고하는 방법
꼬리 재귀를 사용하기 힘든 상황에서 재귀 함수의 장점을 놓치고 싶지 않다면 일반적인 재귀 함수의 사용을 고려해야 한다. 이때 재귀 함수의 단점을 최소화 시키고 싶다면 탈출 조건을 고려해야 한다.
탈출 조건
앞선 팩토리얼의 일반적인 재귀 함수 형태에서 탈출 조건은 n이 1이 되는 순간이다. n이 1이되는 순간 조건문이 작동하여 1이 리턴되고 미뤄졌던 연산이 순차적으로 진행되 최종적인 값이 나오게 된다.
재귀 함수의 탈출 조건은 base case라 한다. 이는 재귀의 기초라고도 불리는데 문제를 순서와 크기에 따라 같은 조건을 적용하여 작은 부분으로 쪼갤때 더이상 쪼개지지 않는 가장 쉬운 문제를 의미한다.
문제를 쪼개기
주어진 문제를 일정 기준에 따라 더 작은(해결하기 더 쉬운)부분으로 쪼갠다. 재귀 함수는 쪼개진 쉬운 문제를 순차적으로 해결하는 방식이다. 가장 큰 단위에서 문제 해결에 사용한 해결 방법을 작은 단위에도 동일하게 적용할 수 있다면 올바르게 문제를 쪼갠 것!
