재귀(Recursion)란?
재귀 함수(Recursion Function)란?
재귀의 설명 그대로 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.
그렇기에 특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.
우리가 흔히 알고 있는 반복문은 for, while 등이 있는데, 이러한 반복문으로 구현가능한 로직은 모두 재귀함수로도 가능하고 그 반대 역시 가능하다.
이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)이다.
int factorial(int n) {
if (n === 1) {
return 1;
}
return n * factorial(n-1);
}
Java
복사
팩토리얼 함수
가령 예를 들어 인자로 5을 넣는다면 5 * 4 * 3 * 2 * 1 이 되는 것이다.
이를 좀 더 이해하기 쉽게 그림으로 해당 코드가 수행될 때의 콜스택을 살펴보자.
factorial(5)를 호출했을 경우의 콜스택 변화
함수를 호출할 때마다 콜스택에는 함수의 매개변수,지역변수,반환주소값등을 모두 저장하게 되는데, factorial(5)를 호출하게되면 반환타입 부분에서 5 * factorial(5-1) 이 수행되면서 factorial(4)가 호출되고 반환을 기다리게된다.
그럼 그 다음에는 factorial(4) 에 대한 지역변수, 매개변수, 반환주소값등이 콜스택에 쌓이게되는데, 이렇게 factorial(5), factorial(4), factorial(3), factorial(2), factorial(1) 까지 차곡차곡 콜스택이 쌓이게 되고, factorial(1)에서 if(n === 1)이라는 분기에 걸리면서 드디어 해당 콜스택이 하나씩 수행되며 사라질 것이다.
Stack overflow
이러한 재귀 함수 사용에는 스택 오버플로우(stack overflow)를 주의해야한다.
예를 들어, 위에서 작성한 factorial에서 if(n===1)이 빠진다면 어떻게 될까?
int factorial(int n) {
return n * factorial(n-1);
}
Java
복사
n이 1일 경우 멈춰야 하는 해당 함수는 이제 멈추지 않고 -1, -2, -3, .... n까지 무한대로 실행되게 되는데, 사실상 컴퓨터의 메모리에는 한계가 있으니 무한대는 불가능하고 스택 오버플로우 문제가 발생 하게 된다.
자바에서 해당 코드를 수행하면 콘솔창에 뜨는 StackOverflowError 을 확인할 수 있을 것이다.
재귀함수의 장단점
장점
1.
변수를 여럿 만들 필요가 없다.
예를들어 현재 상태를 저장해야 할 경우 tmp 변수를 만들기보다 상태를 메서드를 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일 수 있습니다.
2.
while문이나 for문같은 반복문을 사용하지 않아도 되기에 코드가 간결해집니다.
단점
1.
지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 process stack에 저장해야합니다. 그리고 이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 되고, 이는 속도 저하로 이어진다.
2.
함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 된다.
재귀함수의 단점 해결 방법 - 꼬리 재귀(tail call recursion)
재귀 함수의 가장 큰 문제가 자기 자신을 호출한 뒤 결과를 기다리면서 생기는 콜스택의 부하로 인한 메모리낭비였는데, 꼬리 재귀라는 개념을 이용하면 재귀 호출이 끝나는 시점에서 아무 일도 하지 않고 바로 결과를 반환하도록 하는 방법으로 함수의 상태 유지 및 추가 연산을 하지 않기에 스택 오버 플로우 해결할 수 있다.
// Basic Recursion
int factorial(int n, int total) {
if (n === 1) {
return 1;
}
return n * factorial(n-1);
}
// Tail Recursion
int factorial(int n, total) {
if (n === 1) {
return 1;
}
return factorial(n - 1, n * total);
}
Java
복사
기존 재귀함수 factorial과 꼬리재귀 factorial 함수
차이점을 잘 보면 반환부분 코드가 달라졌다. 꼬리 재귀의 핵심은 반환부에 연산이 없어야 한다는 점이다.
이렇게 반환부에 연산이 없도록 구현을 한다면 컴파일러는 꼬리 재귀 최적화를 지원하여 자체적으로 재귀함수를 해석해서 반복문으로 변경해서 실행한다.
