재귀(recursion)와 반복(iteration)
알고리즘 dp 문제에서 자주 사용하는 방식으로 재귀와 반복이 있다. 보통 Bottom-up방식으로 구현하고 싶으면 반복문을 사용하고, Top-down방식으로 구현하고 싶으면 재귀를 사용하는 경우가 많다. 다음 문제가 나왔을 때 보는 관점에 따라 구현이 달라진다.
예를 들어, 정수 X에 사용할 수 있는 연산이 다음과 같이 세 가지가 있다고 하자.
1. X가 3으로 나누어 떨어지면,3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하라.
재귀 (Top-down) 풀이
정수 N → 1로 가는 길이 세 가지 갈래길로 나눠져있으니 재귀로 N부터 1까지 가는 길을 탐색하자.
// Top-down
void nToOne(int num, int cnt) {
if(num==1) {
ans = Math.min(ans, cnt);
return;
}
if(cnt >= ans) return;
if(num%3==0) {
toOne(num/3, cnt+1);
}
if(num%2 ==0) {
toOne(num/2, cnt+1);
}
toOne(num-1, cnt+1);
}
반복문 (Bottom-up) 풀이
정수 1 → N으로 가는 길이 세 가지 갈래길로 나눠져있으니 반복문으로 1부터 N까지 순차적으로 탐색하자.
// Bottom-up
int oneToN(int num) {
int[] dp = new int[num+1];
for(int i=2; i<num+1; i++) {
dp[i] = dp[i-1]+1; // -1
if(i%2==0) {
dp[i] = Math.min(dp[i], dp[i/2]+1);
}
if(i%3==0) {
dp[i] = Math.min(dp[i], dp[i/3]+1);
}
}
return dp[num];
}
Top-down vs Bottom-up
보통 dp를 접근할 때 Top-down을 많이 사용한다. 왜냐하면 서브문제를 하나씩 하나씩 풀어나가는 방식(Bottom-up)보다는 전체의 문제에서 분할해나가는 과정이 훨씬 자연스럽게 접근이 가능하기 때문이다. 그렇다고 Top-down만을 고집해서는 안된다.
효율성을 고려해야 할 경우는 Bottom-up이 더 좋다. Top-down은 재귀를 사용하는 방식이기 때문에 Stack에 많은 재귀함수가 쌓이게 될 경우 StackOverflow가 발생할 수 있다.
재귀는 입력값이 너무 크거나 종결 조건을 실수하면 무한 재귀가 호출 될 수 있다. 정확히 기본 케이스에 수렴하는 방식으로 문제를 줄여나가야 한다. 그렇지 않으면 다음과 같이 CPU 크래시가 발생할 수 있다.
반복문을 사용하면 for문으로 예측가능한 범주 내에 실행이 가능하고 만약 조건을 잘못 설정하여 무한루프가 발생한다고 해도 언제든 프로그램을 중지할 수 있다.
꼬리 재귀(Tail Recursion)
Top-down 방식으로 풀이하거나 혹은 다른 프로그램을 설계할 때 재귀로 구현하고 싶은 데 위와 같은 StackOverflow로 마음이 편치 않을 수 있다. 그래서 보통 꼬리 재귀 최적화(TCO; Tail-Call Optimization)를 이용한다. 꼬리 재귀를 이용하면 오버헤드를 피하면서 재귀를 자유롭게 사용할 수 있다.
꼬리 재귀 함수는 마지막 동작이 자신을 호출하는 함수일 뿐이다. Kotlin, Scala를 이용하면 꼬리 재귀를 쉽게 만들 수 있다. 스칼라나 코틀린 컴파일러는 꼬리 재귀를 감지하고 함수 매개변수를 새 값으로 업데이트한 후 함수의 시작 부분으로 되돌아가는 점프로 대체한다. 이 외에도 C++, C#, Swift에서도 꼬리 재귀를 지원한다.
그러나 자바에서는 지원하지 않는다. 같은 JVM기반 언어인 스칼라나 코틀린은 지원하는 데 왜 자바는 안되는 것일까? 일단 꼬리 재귀에 대해서 부터 살펴보자
일반 재귀
int recursiveFactorial(int n) {
if (n == 1)
return 1;
return n * recursiveFactorial(n - 1);
}
꼬리 재귀
int tailFactorialFunc(int n, int acc) {
if (n == 1)
return acc;
return tailFactorialFunc(n - 1, acc * n);
}
Java에서 컴파일된 일반 재귀와 꼬리 재귀
Java로 꼬리 재귀를 작성하여도 다음과 같이 컴파일한 클래스 파일을 보면 그냥 일반 재귀와 똑같음을 볼 수 있다. 꼬리 재귀로 작성된 함수는 계산을 함수 매개변수 내(acc*n)에서 진행할 뿐이다. 큰 값으로 실행하면 둘 다 Stack에 함수가 쌓이면서 StackOverflow가 발생하게 된다.
int recursiveFactorial(int n) {
return n == 1 ? 1 : n * recursiveFactorial(n - 1);
}
int tailFactorialFunc(int n, int acc) {
return n == 1 ? acc : tailFactorialFunc(n - 1, acc * n);
}
Kotlin에서 컴파일된 꼬리 재귀
위 Java에서 구현했던 방법과 똑같이 Kotlin으로도 꼬리 재귀를 작성해보자. tailrec 키워드를 추가하여 컴파일러에게 해당 코드는 꼬리 재귀임을 명시해줘야 한다.
fun tailFactorial(n: Int): Int {
return tailFactorialFunc(1, n)
}
tailrec fun tailFactorialFunc(acc: Int, n: Int): Int {
if (n == 1) {
return acc
}
return tailFactorialFunc(acc * n, n - 1)
}
그러면 컴파일러 최적화(Optimization) 기능이 다음과 같이 코드를 바꿔준다. 해당 코드는 컴파일된 코틀린 바이트코드 파일(클래스 파일)을 다시 자바 파일로 디컴파일한 코드이다.
재귀 호출은 사라지고 while 반복문으로 최적화되어 있는 것을 확인할 수 있다. Kotlin은 꼬리 재귀 최적화 기능을 지원해주기 떄문에 이러한 결과가 가능한 것이다. 그래서 StackOverflow 걱정없이 재귀 호출 알고리즘을 작성할 수 있다.
public static final int tailFactorial(int n) {
return tailFactorialFunc(1, n);
}
public static final int tailFactorialFunc(int acc, int n) {
while(n != 1) {
int var = acc * n;
--n;
acc = var;
}
return acc;
}
Java 컴파일러가 꼬리 재귀 최적화를 지원하지 않는 이유
Brian Goetz(Oracle의 자바 언어 아키텍트)는 이 비디오에서 다음과 같이 설명하고 있다.
jdk 클래스들에는 몇몇 보안에 민감한 메소드들이 있는데, 이 메소드들은 메소드 호출을 누가 했는지를 알아내기 위해 jdk 라이브러리 코드와 호출 코드간의 스택 프레임 갯수에 의존한다. 스택 프레임의 수의 변경을 유발하게 되면 이 의존관계를 망가뜨리게 되고 에러가 발생할 수 있다. 이게 멍청한 이유라는 것을 인정하며, JDK 개발자들은 이 메커니즘을 교체해 오고 있다.
"그리고 추가적으로, tail recursion이 최상위 우선순위는 아니지만, 결국에는 지원될 것이다." 라고 말했다.
결국은 어떠한 코드들이 스택 프레임 갯수에 의존하고 있고 스택 프레임 수 변경을 유발하는 코드가 JDK에 존재하게 되면 에러가 발생할 수 있기 때문에 Java는 TCO를 지원해주고 있지 않다고 볼 수 있다. 결국은 에러 발생 우려를 제외하면 지원하지 않을 이유가 없다는 뜻이다. 영상이 14년도로 8년이 지난 지금도 업데이트가 안된 것을 보면 어쩌면 꼬리 재귀 기능 자체에 대한 수요가 많지는 않은 것 같다. 스택을 활용하여 메모리 소유권 개념을 만든 Rust 지원안해주는 것을 보고 그러려니 했지만 자바 너는 왜?
Java 8 람다식과 함수형 인터페이스로 꼬리 재귀 최적화(TCO) 구현하기
재귀를 사용할 때 가장 조심해야 할 점은 스택 오버플로의 위험이다. TCO를 사용하면 재귀 호출의 결과에 대해 추가 계산을 수행하는 일반 재귀와는 달리 직접 꼬리 호출로 변환하여 큰 입력값을 효율적으로 처리할 수 있게 해준다.
Java는 컴파일러 수준에서 TCO를 직접 지원하지 않지만 JAVA 8에 람다식과 함수형 인터페이스가 도입 되어 몇 줄의 코드로 이 개념을 구현할 수 있다. 이 재귀 코드를 보면 리턴 값에 대해 재귀 함수 외에 추가 계산이 없다. 또한 factorialTailRec() 메서드는 람다식으로 래핑되어 eager 호출이 아닌 lazy 호출로 실행된다.
- 재귀의 종결 조건은 number == 1일 때, done() 메서드를 호출한다.
- call()메서드는 number → numer-1로 기본 케이스를 0으로 수렴하도록 문제를 줄여나간다.
public static TailCall<Integer> factorialTailRec(final int factorial, final int number) {
if (number == 1) {
return TailCalls.done(factorial);
}
return TailCalls.call(() -> factorialTailRec(factorial * number, number - 1));
}
이것이 어떻게 작동하는지 이해하기 위해 메서드 내부를 살펴봐야 하므로 TailCall 인터페이스와 TailCalls 편의 클래스를 먼저 자세히 살펴보자.
1. TailCall 함수형 인터페이스 만들기
@FunctionalInterface
interface TailCall<T> {
TailCall<T> apply();
default boolean isComplete() {
return false;
}
default T result() {
throw new Error("not implemeted");
}
default T invoke() {
return Stream.iterate(this, TailCall::apply)
.filter(TailCall::isComplete)
.findFirst()
.get()
.result();
}
}
2. TailCalls 편의 클래스 만들기
편의 클래스는 다른 작업을 단순화하기 위해 만든 클래스이다
class TailCalls {
public static <T> TailCall<T> call(final TailCall<T> nextCall) {
return nextCall;
}
public static <T> TailCall<T> done(final T value) {
return new TailCall<T>() {
@Override public boolean isComplete() { return true; }
@Override public T result() { return value; }
@Override public TailCall<T> apply() {
throw new Error("not implemented");
}
};
}
}
3. 꼬리 재귀 함수 사용하기
꼬리 재귀가 정상적으로 동작한다. 기존에 일반 재귀 함수로 20000을 넣으면 StackOverflow가 발생하였지만 지금은 Stack이 터지지 않는다. 그러나 int형이 결과 값을 감당하지 못하고 0을 출력하고 있다.
public static int factorial(final int number){
return factorialTailRec(1, number).invoke();
}
public class Main {
public static void main(String[] args) {
int tailResult = FactorialToInt.factorial(10); // 3628800
int tailResult2 = FactorialToInt.factorial(20000); // 0
}
}
4. Arithmetic Overflow 고쳐주기
Arithmetic Overflow를 고치기 위해서는 int형을 BigInteger로 바꿔주면 된다.
class FactorialToBigInteger {
final static BigInteger ONE = BigInteger.ONE;
final static BigInteger TEN = new BigInteger("10");
final static BigInteger TWENTY_K = new BigInteger("20000");
private static BigInteger decrement(final BigInteger number){
return number.subtract(ONE);
}
private static BigInteger multiply(final BigInteger first, final BigInteger second){
return first.multiply(second);
}
private static TailCall<BigInteger> factorialTailRec(final BigInteger factorial, final BigInteger number) {
if (number.equals(ONE)) {
return TailCalls.done(factorial);
}
return TailCalls.call(() -> factorialTailRec(multiply(factorial, number), decrement(number)));
}
public static BigInteger factorial(final BigInteger number){
return factorialTailRec(ONE, number).invoke();
}
}
5. 피보나치 함수로 테스트하기
원래 fibo(20,000)정도를 호출하면 StackOverFlow가 발생한다. 그런데 위와 같이 꼬리 재귀 함수를 구현하여 사용하면 오버플로가 발생하지 않고 정상적으로 값이 출력되는 것을 확인할 수 있다.
public class Main {
public static void main(String[] args) {
try{
System.out.println(String.format("%.30s...", FactorialToBigInteger.factorial(TWENTY_K)));
}catch (VirtualMachineError ex){
System.out.println(ex);
}
}
}
// 181920632023034513482764175686...
실습한 내용은 github에서 확인할 수 있습니다.
참고
http://wiki.sys4u.co.kr/display/SOWIKI/Tail+call+Optimization
'Dot Programming > Java' 카테고리의 다른 글
| JVM 2 - Runtime Data Area 구조 (0) | 2022.05.31 |
|---|---|
| JVM 1 - Java Architecture, JVM Specification (0) | 2022.05.31 |
| [Play with Java] 자바에서 오버플로우 없이 2개의 INT 평균 구하기 (0) | 2022.02.13 |
| [Java] 자바 서블릿과 서블릿 컨테이너 2 - MVC 패턴 도입 (0) | 2022.02.10 |
| [Java] 자바 서블릿과 서블릿 컨테이너 1 - 웹 서버 한계와 WAS 등장 (0) | 2022.02.10 |
