[Java][Algorithm] 재귀호출

들어가기전에

알고리즘에서 흔히 사용되었던 재귀호출에 대해 면접에서 질문을 받은 적이 있다. 재귀함수 개념은 알고있었지만, 설계시 생각해야 되는 점이 무엇인지에 대해 제대로 말을 못했다는 점에서 간단히 정리하고 넘어가려고 한다.

재귀호출이란?

재귀호출이란 일정 조건을 만족할 경우 자신을 호출하는 것을 말한다.
우리가 자주 봤던 피보나치와 팩토리얼 메서드가 재귀호출을 사용하는 메서드에 속한다.

// 피보나치 수열
public static int fibonacci(int n) {
    if (n<2) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

// 팩토리얼
public static int factorial(int n) {
    if (n==0) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

재귀호출을 사용하는 이유

1. 가독성이 좋다.
   for문과 같은 반복문을 사용하는 것보다 알고리즘을 기술한 그대로 표현가능하기 때문에 코드의 직관적이해가 가능하다.

2. 변수의 사용을 줄여준다.
   처음에 받은 변수를 그대로 다음 호출에도 사용하기 때문에 생각치 못한 변수 사용을 줄여 오류가 발생할 수 있는 가능성을 줄여주며, 변수가 가질 수 있는 값의 종류 또는 범위도 제한하게 되어 함수를 단순하게 만들고, 불변적으로 유지될 수 있도록 한다.

재귀 함수 설계시 고려해야 하는 부분

• 순환되지 않고 종료되는 case가 무조건 존재해야한다. 이것을 주로 base case라고 한다.
• 명시적 매개변수를 사용해야한다.

재귀호출의 단점

자바에서 재귀를 쓰지 않는 것을 권장한다. 왜냐면 잘못 사용할 경우 무한루프에 빠져 스택오버플로우가 발생될 수 있고, 무한루프에 빠지지 않더라도 함수의 매개변수/지역변수/리턴 값 함수의 위치가 메모리에 쌓이면서 stack이 점점 쌓여 이 역시 스택오버플로우를 발생시킬 수 있다는 점이다.

재귀 호출 최적화 - Tail Call

스택 오버 플로우를 막는 방법 중에 테일 콜이 있다.
이 테일 콜은 꼬리 호출이라고 불린다. 재귀 호출이 스택 오버플로우가 생기는 이유는 원래 자리로 돌아와서 해야할 일이 남아 있는 경우 (모든 일을 처리한게 아니라 다시 돌아가서 마지막으로 계산해야하는 것이 있는 경우) 원래 자리의 정보를 stack에 쌓게 되는데, 이 때 stack이 넘쳐 오버플로우가 생기는 것이다.
Tail Call은 함수를 호출해서 값을 반환 받은 후 아무 일도 하지 않고 바로 반환하게 하기 위해 논리적으로 가장 마지막(꼬리) 위치에서 함수를 호출하는 방식을 말한다.

TCO (꼬리 호출 최적화)

Tail Call을 하기 위해서는 return 받고나서 아무것도 수행하는 게 있으면 안된다.
왼쪽 처럼 계속해서 다른 값을 더하게 저장하고 있으면 안되고, 오른쪽과 같이 return 한 후 마무리가 되어야한다.

stack은 아래와 같이 변수와 return을 저장하고 계속 쌓이게 되는데, 이때 Tail Call 방식을 사용하게 되면 스택이 쌓이지 않고, 하나의 함수 호출 스택을 재사용 할 수 있다.

여기서, Tail Call을 사용하게 된다면 n과 m 파라미터를 바꿔서 계속 연산해주면 되고, 그 전의 값인 n=10, m= 0 은 가지고 있지 않아도 된다.

Factorial을 Tail Recursion으로 바꾸기

Java에서는 아래와 같이 바꿀 수 있다. 이런 방식을 사용하는 것은 프로그래머의 영역보다는 언어가 제공을 해야한다고 한다.

public static TailCall<Integer> factorialTailRec(final int factorial, final int number) {
    if (number == 1) {
        return done(factorial);
    } else {
        return call(() -> factorialTailRec(factorial * number, number - 1));
    }
}

Reference

추가적인 내용은 아래를 참조하시면 더 도움 될 듯 합니다.
https://leejaedoo.github.io/optimizing_recursions/
https://incheol-jung.gitbook.io/docs/study/functional-programming-in-java-8/chap-07.