[모던 자바] 재귀와 반복

재귀와 반복

순수 함수형 프로그래밍 언어에서는 while, for 같은 반복문을 표함하지 않는다.

이러한 반복문 때문에 변화가 자연스럽게 코드에 스며들 수 있기 때문이다.

예를 들어 while 루프의 조건문을 갱신해야 할 때가 있다. 그렇지 않으면 루프가 아예 실행되지 않거나 무한으로 반복할 수 있다. 이외의 일반적인 상황에서는 루프를 안전하게 사용할 수 있다.

 

함수형 스타일에서는 다른 누군가가 변화를 알아차리지만 못한다면 아무 상관이 없다고 설명했다.

즉, 지역변수는 자유롭게 갱신할 수 있다.

Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String name = it.next();
}

위 코드에서 호출자는 변화를 확인할 수 없으므로 아무 문제가 없다.

하지만 다음 코드처럼 for-each 루프를 사용하는 알고리즘은 문제가 될 수 있다.

int maxNumber = 0;
public void getMaxNumber(List<Integer> numbers) {
    for (Integer number : numbers) {
         if (maxNumber < number) maxNumber = number;
    }
}

루프의 바디에서 함수형과 상충하는 부작용이 발생한다.  즉, 루프 내부에서 프로그램의 다른 부분과 공유되는 maxNumber 객체를 변화시킨다.

 

그럼 어떻게 프로그램을 구현해야 할까?

이론적으로 반복을 이용하는 모든 프로그램은 재귀를 이용하면 변화가 일어나지 않는다.

재귀를 이용하면 루프 단계마다 갱신되는 반복 변수를 제거할 수 있다.

1부터 n까지의 곱을 반환하는 팩토리얼 함수가 있다고 가정해보자.

public int factorial(int n) {
    int r = 1;
    for (int i = 1; i <= n; i++) {
        r *= i;
    }
    return r;
}

이 코드를 반복과 재귀 방식으로 구현하면 아래와 같다.

public int factorial(int n) {
    return n == 1 ? 1: n * factorialIterative(n - 1);
}

Java8에서는 스트림으로 좀 더 단순하게 팩토리얼을 정의할 수 있다.

public int factorial(int n) {
    return IntStream.rangeClosed(1, n)
        .reduce(1, (int a, int b) -> a * b);
}

효율성 측면에서는 함수형 프로그래밍의 장점이 분명히 있지만 무조건 반복보다는 재귀가 좋다고 주장은 주의해야 한다. 일반적으로 반복코드보다 재귀 코드가 더 비싸다.

재귀 함수를 호출할 때마다 호출 스택에 각 호출시 생성되는 정보를 저장할 새로운 스택 프레임이 만들어지기 때문이다.

즉, 일반적인 반복코드에 비레해서 메모리 사용량이 증가한다. 따라서 큰 입력값을 사용하면 SlackOverFlowError가 발생할수도 있다.

 

이러한 문제를 함수형 언어에서는 꼬리 호출 최적화(tail-call optimization)라는 해결책을 제공한다.

public int factorialTailRecursive(int n) {
    return factorial(1, n);
}
public int factorial(int acc, int n) {
    return n == 1 ? acc : factorial(acc * n, n - 1);
}

이전 코드는 마지막에 수행한 연산은 n과 재귀 호출의 결과값의 곱셈이다.

반면에 꼬리 호출 최적화가 적용된 코드에서는 재귀 호출이 가장 마지막에 이루어진다.

반복적 재귀 호출 / 꼬리 호출 최적화 재귀 호출

안타깝게도 Java는 이와 같은 최적화를 제공하지 않는다.

그럼에도 여전히 고전적인 재귀보다는 여러 컴파일러 최적화 여지를 남겨둘 수 있는 꼬리 재귀를 적용하는 것이 좋다. 

결과적으로 순수 함수형을 유지하면서도 유용성 뿐 아니라 효율성까지 두 마리 토끼를 모두 잡을 수 있다.

 

결론적으로는 Java8에서는 반복을 스트림으로 대체해서 변화를 피할 수 있다.

실제로 재귀를 이용하면 좀더 쉽게 읽고, 쓰고 이해할 수 있는 예제를 만들수 있고, 반복을 재귀로 바꾸면 효율성 부분은 조금 떨어지지만 더 간결하고, 부작용이 없는 알고리즘을 만들 수 있다.

약간의 실행시간 차이보다는 프로그래머의 효율성이 더 중요할 때도 많다.