728x90

재귀 함수(Recursion Function)

재귀 함수는 내부적으로 스택(Stack)을 이용한다. JVM(Java Virtual Machine) 의 메모리인 Runtime Data Areas 영역에 스택 영역이 존재한다. 자바에서 함수를 호출하게 되면 함수에 대한 정보들이 스택 공간에 적재되기 때문에, 재귀 함수는 스택 자료구조를 이용한다고 볼 수 있다.

재귀 함수는 자기 자신을 다시 호출하는 함수를 의미 하는데, 재귀 함수를 제대로 이해하기 위해선 다음과 같은 내용에 대한 이해가 되어있어야 한다.

JVM 메모리 스택 영역
JVM 메모리 힙 영역
스택 자료 구조
Call Frame(Call Stack)

먼저, 이 부분에 대한 이해를 다루기 전에 팩토리얼(Factorial) 구현을 예시로 들어서 재귀 함수의 특징과 장점을 먼저 다루고 가겠다.

팩토리얼(Factorial)

팩토리얼(Factorial)은 재귀 함수를 이용하는 대표적인 예제 중 하나이다.

팩토리얼(Factorial) : n! > 1 x 2 x 3 x ... x (n-1) x n

재귀 함수의 첫 번째 특징은 종료 조건이 있어야 한다는 것이다. 종료 조건을 명시하지 않으면 무한 루프에 빠져 Stack Overflow 현상이 발생할 수 있다. 두 번째 특징은 점화식을 작성할 수 있다는 것이다. 팩토리얼의 점화식을 작성하면 다음과 같다.

n 이 0이거나 1일때 : factorial(n) = 1
n 이 1보다 클 때 : factorial(n) = n x factorial(n-1)

public static int factorialRecursive(int n) {
    // n이 1 이하인 경우 1을 반환
    if (n <= 1) return 1;
    // n! = n * (n - 1)!를 그대로 코드로 작성하기
    return n * factorialRecursive(n - 1);
}

재귀 함수를 사용했을 때의 장점은 코드가 간결해진다는 것이다. 이렇게 간결해진 이유는 재귀 함수가 수학의 점화식을 그대로 소스코드로 옮겼기 때문이다. 이 점화식은 다이나믹 프로그래밍(Dynamic Programming)을 배울 때 중요하다.

재귀 함수 특징

지금까지 배운 재귀 함수의 특징을 정리하자면 다음과 같다.

스택 사용
종료 조건 필수
점화식으로 표현 가능

스택(Stack) 과 재귀(Recursion)

위에 내용만 보고 재귀를 다 이해했다고 착각하면 안된다. 위에서 다룬 내용은 특징 몇가지를 통해 재귀를 어떻게 구현하는 지를 배운 것이고, 이번에 배울 것은 재귀가 스택으로 동작한다는 것을 이해하는 것이다.

위에서 배운 팩토리얼을 다시 예시로 들겠다. 이 예제는 재귀를 이해하기 위한 선행 지식을 배운 후에 사용할 것이다.

public static int factorial(int n) {
    System.out.println(Thread.currentThread().getName()); // 현재 실행중인 스레드 이름 출력
    return n <= 1 ? 1 : n * factorial(n-1);
}

public static void main(String[] args) {
    System.out.println(factorial(5));
}

자, 재귀를 제대로 이해하기 위해서 JVM 메모리 스택, 힙 영역, 스택 자료 구조, Call Frame 에 대해서 이해하고 있어야 한다고 했다.

JVM 메모리 스택 영역

자바에서는 스레드가 생성 될 때 마다 스택 영역이 개별적으로 생성된다.
스레드가 메서드 호출 시, 지역변수, 매개변수 등이 저장된다.
Heap 영역에 생성된 Object 타입 | 데이터 의 참조 변수(Reference Variable)가 할당된다.
- Ex. String ref = "abc";
- 실제로 Heap 영역에는 String | "abc" 이런식으로 들어가고, ref 의 참조 변수가 stack 에 할당된다.
원시 타입의 데이터가 값과 함께 할당된다.
지역변수들은 scope 에 따른 visibility 를 가진다.
가장 마지막에 호출한 함수가 종료 되어야 이전에 호출한 함수들도 종료가 된다.

JVM 메모리 힙 영역

Heap 영역에는 주로 긴 생명주기를 가지는 데이터들이 저장된다.
애플리케이션의 모든 메모리 중 stack 에 있는 데이터를 제외한 부분이라고 보면 된다.
모든 Object 타입(Integer, String, ArrayList, ...)은 heap 영역에 생성된다.
몇개의 스레드가 존재하든 상관없이 단 하나의 heap 영역만 존재한다.
Heap 영역에 있는 오브젝트들을 가리키는 레퍼런스 변수가 stack 에 올라가게 된다.

스택(Stack) 자료 구조

LIFO(Last In First Out)
push(), pop()
한 쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조

Call Frame

재귀 함수는 함수가 호출될 때마다 Call Frame(호출 프레임)의 정보들이 스택 메모리에 저장된다.
- 호출 함수의 return address
  - 스택에서 가장 마지막에 호출한 함수가 종료 되어야 이 전에 호출한 함수들도 종료가 된다. 호출 함수의 return address 가 있기에 돌아올 위치를 알 수 있는 것이다.
- 피호출 함수의 매개변수 와 지역변수

자, 다시 예제로 돌아와서 위 코드의 실행 결과는 다음과 같다.

main 
main
main
main
main
120

호출된 재귀 함수들이 현재 main 스레드 위에서 동작하는 것을 볼 수 있다. (즉, 스레드가 현재 1개이다.) 그러면 위에서 배운 개념을 적용하면 생성된 스택 영역도 1개인 것이다.

그림으로 스택과 재귀의 동작 과정을 살펴보자. 그림에서 색깔이 다른 이유는 다른 scope 를 의미한다. 따라서 스택에 n 이 값이 여러개 있더라도 scope 가 다르면 사용할 수 없다.

잘 보면 맨 아랫부분을 제외하고 나머지 return address 가 b 로 통일된 것을 볼 수 있는데, 팩토리얼 예제에서 재귀 함수가 호출되는 라인이 항상 같기 때문이다.

Stack Overflow

재귀 함수는 호출 시 마다 함수의 지역변수, 매개변수, 리턴 후 돌아갈 위치, 리턴 값 등을 스택에 저장한다. 따라서 무리하게 호출을 하다보면 스택 공간이 다 차버리는 스택 오버플로우(Stack Overflow)현상이 발생할 수 있다.

꼬리 재귀(Tail Recursion)

꼬리 재귀는 재귀 함수의 장점은 살리고, 단점을 보완하는 방법 중 하나이다

꼬리 재귀 최적화를 위한 조건
- 재귀 함수를 꼬리 재귀 방식으로 구현할 것
- 컴파일러가 꼬리 재귀 최적화를 지원할 것

컴파일러가 꼬리 재귀 최적화를 지원하지 않는다면, 꼬리 재귀 방식으로 구현을 해도 일반 재귀 처럼 동작할 것이다.

꼬리 재귀는 재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환되도록 하는 방법이다. 이 방식을 사용하면 이전 함수의 상태를 유지하지도 않고 추가 연산을 하지도 않아서 스택이 넘쳐나는 문제를 해결할 수 있게 된다.

꼬리 재귀 함수는 이름처럼 항상 함수의 꼬리부분(마지막)에서 실행되는데, return 되기 전에 값이 정해지며 호출당한 함수의 결과값이 → 호출하는 함수의 결과값 으로 반환된다.

// 일반 재귀로 구현한 팩토리얼
public int factorial(int n) {
    return n <= 1 ? 1 : n * this.factorial(n - 1);
}

일반적인 재귀의 경우 factorial(3)을 호출 했다고 하면 마지막에 호출된 재귀 함수 값이 1이면 그 값을 다음 스택에 넘겨서 2 * 1을 계산하게 하고, 그 결과를 또 다음 스택에 넘겨서 3 * 2 를 계산하게하여 결과를 도출한다. 일반 재귀의 마지막 부분은 아래처럼 생겼었다. factorial(n-1) 이 바로 호출당한 함수인데, 이 함수는 스택에 쌓였다가 빠져 나올 때 원래 자기 자리로 돌아가서 앞쪽의 n 과 곱해져야 한다. 즉, return address 가 필수이다.

일반 재귀 방식에 대한 컴파일러의 해석은 동일하다.

// 컴파일된 코드 : 동일하다
public int factorial(int n) {
    return n <= 1 ? 1 : n * this.factorial(n - 1);
}

다음은 꼬리 재귀 방식이다.

public int factorialTail(int n, int total) {
    return n == 1 ? total : factorialTail(n - 1,  n * total);
}

public int factorial(int n) {
    return factorialTail(n, 1);
}

꼬리 재귀의 핵심은 재귀 호출 이후 추가적인 연산을 요구하지 않도록 구현 하는 것이다.

꼬리 재귀의 마지막 부분을 보면 factorialTail(n - 1, n * total) 따로 연산 같은 작업을 추가로 하지 않고 반환만 한다. 따라서 굳이 자기 자리를 기억하지 않아도 된다. 즉, 스택에 return address 를 저장할 필요가 없어진다.

위 코드에 대한(꼬리 재귀를 지원하는) 컴파일러의 해석은 다음과 같다.

int factorialTail(int n) {
    int total = 1;
    do {
        if(n == 1) return;
        total = total * n;
        n = n - 1;
    } while(true);
}

재귀호출은 사라지고, do-while 문을 이용하는 코드로 최적화되어 있는 것을 확인할 수 있다. 즉, 내부적으로 재귀 함수를 반복문으로 변경되어 실행이 된다. 따라서, Stack Overflow 에 대한 위험이 없다고 하는 것이다.

Java 와 꼬리 재귀 최적화

C++, C#, Kotlin, Swift 는 꼬리 재귀 최적화를 지원하며, JavaScript 는 ES6 스펙에서 지원한다고 한다. Scala 는 JVM 위에서 동작하는데, 꼬리 재귀 최적화를 지원한다고 한다. 하지만 Java 는 꼬리 재귀 최적화를 직접적으로 지원하지 않는다.

자바에서 진짜 꼬리 재귀 최적화를 지원하지 않는지 확인하기 위해 테스트 해보았다. 컴파일러의 해석은 다음과 같다.

// 컴파일된 코드 : 동일하다
public int factorial(int n) {
    return n <= 1 ? 1 : n * this.factorial(n - 1);
}

지원하지 않는 이유
- JDK 클래스에는 보안에 민감한 메소드가 있다고 한다. 이 메소드들은 메소드 호출을 누가 했는지 알아내기 위해 JDK 라이브러리 코드와 호출 코드간의 스택 프레임 갯수에 의존한다. 스택 프레임 수의 변경을 유발하게 되면 이 의존관계를 망가뜨려 에러가 발생할 수 있다.
Java에서 꼬리 재귀 사용하기?
- Java 는 컴파일러 레벨에서는 직접적으로 꼬리 재귀 최적화를 지원하지는 않지만, Java 8의 람다식과 함수형 인터페이스(Functional Interface)로 꼬리 재귀와 같은 컨셉을 적용해볼 수 있다고 한다.

Java 에서 꼬리 재귀 구현하기

Java 8의 람다식과 함수형 인터페이스(Functional Interface)로 구현해보았다.

/**
 * TailCalls Convenience Class
 */
class TailCalls {

    public static TailCall call(final TailCall nextCall) {
        return nextCall;
    }

    public static TailCall done(final int value) {
        return new TailCall() {
            @Override
            public boolean isComplete() { // true 를 반환하여 재귀의 끝을 보고한다.
                return true;
            }

            @Override
            public int result() {
                return value;
            }

            @Override
            public TailCall apply() {
                throw new Error("not implemented");
            }
        };
    }
}

/**
 * default 메서드를 이용하여 구현
 */
@FunctionalInterface
interface TailCall {

    // 실행 대기 중인 다음 TailCall 인스턴스를 반환
    TailCall apply();

    // 단순히 false 를 반환 : false 라는 것은 아직 대기중이라는 의미가 된다.
    default boolean isComplete() {
        return false;
    }

    default int result() {
        throw new Error("not implemented");
    }

    default int invoke() {
        return Stream.iterate(this, TailCall::apply)
                .filter(TailCall::isComplete)
                .findFirst()
                .get()
                .result();
    }
}

public class TailRecursiveWithLambda {

    /**
     * factorialTail() 메서드를 호출하면 TailCall 인스턴스와 함께 즉시 반환된다.
     * 핵심 아이디어는 done() 메서드를 호출 하면 재귀가 종료 된다는 신호를 보낸다는 것이다.
     * 반면에 call() 메서드를 사용하는 경우 재귀를 계속하도록 요청하지만 현재 스택 수준에서 한 단계 내려간 후에만 가능하다.
     * @param n 입력값
     * @param total 총 계산한 값
     * @return TailCall
     */
    public static TailCall factorialTail(final int n, final int total) {
        if (n == 1) {
            return TailCalls.done(total);
        } else {
            return TailCalls.call(() -> factorialTail(n - 1, n * total));
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(factorialTail(10, 1).invoke());
    }

}

컴파일러가 해석한 결과는 다음과 같다.

public static TailCall factorialTail(int n, int total) {
    return n == 1 ? TailCalls.done(total) : TailCalls.call(() -> {
        return factorialTail(n - 1, n * total);
    });
}

직접 디버깅을 하면서 Call Frames 를 확인해보면 알겠지만, 일반적인 재귀랑 다르게 하나의 스코프 안에서 n 과 total 의 값이 계산된다는 느낌을 받을 수 있다.

Tail Recursive With Lambda and Functional Interface

Debugging Videos

인텔리제이를 사용한다면 디버깅 모드로 실행하면 Debugger 에 보면 Frames 라고 있는데 Call Frame 들을 볼수 있다.

메모이제이션(Memoization)

자바에서 직접 꼬리 재귀를 사용하도록 구현하는 것은 힘들다라는 것을 느꼈을 것이다. 재귀를 사용하는 알고리즘에서 성능을 극대화 하는 방법 중 하나가 메모이제이션(Memoization)이라는 기법이 있다. 메모이제이션(Memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법(Dynamic Programming)의 핵심이 되는 기술이다.

"이전에 계산한 값을 메모리(배열, 리스트 등)에 저장함으로써 동일한 계산의 반복 수행을 제거" 이 부분이 핵심이다.

이번엔 피보나치 수열(Fibonacci numbers)을 예시로 들어설명하겠다. 문제에서 요구하는 사항은 다음과 같다. 입력값 N 이 주어졌을 때 N 만큼의 피보나치 수열을 구하여 출력하라는 것이다.

피보나치 수열(Fibonacci numbers) : 앞의 2개의 수를 합하여 다음 숫자가 되는 수열

문제
- ```
Input : 5
Output : 1 1 2 3 5
```

Step 1. 가장 허접한 코드

위에서 재귀를 사용하기 전에 점화식을 작성하라고 배웠다. 피보나치 수열의 점화식을 작성하면 다음과 같다.

Fibonacci(n) = Fibonacci(n-2) + Fibonacci(n-1)

public class Main {

    private static int n;

    public static void main(String[] args) {
        initializeInputData();
        for (int i = 1; i <= n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }

    private static void initializeInputData() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
    }

    // 점화식 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
    // 종료 조건 n == 1 || n == 2
    private static int fibonacci(int n) {
        if(n == 1 || n == 2) {
            return 1;
        } else {
            return fibonacci(n - 2) + fibonacci(n - 1);
        }
    }
}

Step 2. 피보나치 결과를 배열에 저장하고 반복하여 출력

public class MainTwo {

    private static int n;
    private static int[] fibonacciResult;

    public static void main(String[] args) {
        initializeInputData();
        fibonacci(n);
        for (int i = 1; i <= n; i++) {
            System.out.print(fibonacciResult[i] + " ");
        }
    }

    private static void initializeInputData() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        fibonacciResult = new int[n + 1];  // 1 1 2 3 ... 따라서 0 번째 인덱스는 필요 없음
    }

    // 점화식 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
    // 종료 조건 n == 1 || n == 2
    private static int fibonacci(int n) {
        if(n == 1 || n == 2) {
            return fibonacciResult[n] = 1;
        } else {
            return fibonacciResult[n] = fibonacci(n - 2) + fibonacci(n - 1);
        }
    }
}

위 코드의 단점은 시간이 오래 걸린다라는 것이다. 입력값 N 을 45 로만 줘도 한 4초가 걸린다. 위 코드를 메모이제이션 기법을 적용하여 1초 미만으로 줄여보겠다.

Step 3. 메모이제이션 적용

public class Memoization {

    private static int n;
    private static int[] fibonacciResult;

    public static void main(String[] args) {
        initializeInputData();
        fibonacci(n);
        for (int i = 1; i <= n; i++) {
            System.out.print(fibonacciResult[i] + " ");
        }
    }

    private static void initializeInputData() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        fibonacciResult = new int[n + 1];  // 1 1 2 3 ... 따라서 0 번째 인덱스는 필요 없음
    }

    // 점화식 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
    // 종료 조건 n == 1 || n == 2
    private static int fibonacci(int n) {
        // Memoization 기법 사용 : 입력값 N 에 대한 결과가 존재하면 메모리에 들어있는 값을 재활용
        if(hasResult(n)) {
            return fibonacciResult[n];
        }

        // 재귀를 이용한 Fibonacci 계산
        if (n == 1 || n == 2) {
            return fibonacciResult[n] = 1;
        } else {
            return fibonacciResult[n] = fibonacci(n - 2) + fibonacci(n - 1);
        }
    }

    // 처음에 배열이 0으로 초기화 되니까 0 보다 크면 이미 계산된 값이 존재한다는 의미
    private static boolean hasResult(int n) {
        return fibonacciResult[n] > 0;
    }
}

fibonacci(5) 를 호출하게되면 점화식에 의해 좌측으로 fibonacci(n - 1) 이 호출되며, 우측으로 fibonacci(n - 2) 가 호출된다.
(코드 상으로는 사실 fibonacci(n - 1) + fibonacci(n - 2) 이렇게 되야 그림이랑 일치한다.) 우측편에서는 fibonacci(3) 까지만 호출되며 아래 노드들은 생기지 않는다. 지금은 5로 해놔서 그렇지만 입력 값이 1000이상이 넘어간다고하면 많은 시간 절약을 할 수 있다.

다음으로

메모이제이션(Memoization)까지 배웠다면 동적 계획법(Dynamic Programming)을 배워서 메모이제이션에 대한 마무리를 지을 차례이다.

References