개요#

재귀함수는 알고리즘을 공부하려면 이미 잘 작성할 수 있어야 한다. 아주 쉬운 알고리즘이 아닌 이상 재귀가 필요한 알고리즘이 많다. 복습한다고 생각하고, 이번 포스트에서는 재귀에 대해 알아보자.¹

재귀 함수(recursive function)#

재귀는 큰 문제를 반복 적용 가능한 작은 문제로 나눠 푸는 방법이다. 보통 어떤 함수가 매개변수만 바꾸어 자기 스스로를 호출하는 방식으로 구현한다.

재귀 함수의 간단한 예: 피보나치 수열#

수학적 정의는 다음과 같다. $\\F_0 = 0,$ $\\F_1 = 1,$ $\\F_n = F_{n-1} + F_{n-2}, (n > 1)$

코드로 봐보자.

public static int fibonacciRecursive(int number){
	if (number <= 1) {
		return number;
	}
	
	return fibonacciRecursive(number - 2) + fibonacciRecursive(number - 1);
}

반복문으로 작성한 피보나치#

모든 재귀는 반복문으로 작성 가능하다. 이번에는 반복문으로 작성된 코드를 보자.

public static int fibonacci(int number) {
    if (number <= 1) {
        return number;
    }
    
    int fib = 1;
    int prev = 1;
    
    for (int i = 2; i < number; ++i) {
        int temp = fib;
        fib += prev;
        prev = temp;
    }
    
    return fib;
}

재귀 함수의 스택 프레임#

일단 fibonacciRecursive(4)를 실행한다고 해보자. 그러면 다음과 같이 스택 프레임이 생긴다고 보자.(컴퓨터 아키텍처에 따라 스택이 내려올수도 있고 올라갈 수도 있는데, 여기서는 내려간다고 가정한다.)

이제 이 함수의 return부분을 풀어보면 다음과 같다.

return fibonacciRecursive(2) + fibonacciRecursive(3);

반환되는 두 함수중 fibonacciRecursive(2)가 먼저 호출되므로 스택 프레임은 다음과 같다.

이제 `fibonacciRecursive(2)`도 풀어보면 다음과 같다.

return fibonacciRecursive(0) + fibonacciRecursive(1);

다시 스택 프레임을 보면

이후 `fibonacciRecursive(0)`은 바로 0을 반환하면서 사라지고, `fibonacciRecursive(1)`을 호출한다.

이후 `fibonacciRecursive(1)`은 1을 반환하면서 사라지고, `fibonacciRecursive(2)` 값을 반환하게 된다. 그리고 `fibonacciRecursive(3)`을 호출한다. 이후 스택 프레임은 다음과 같다.

`fibonacciRecursive(3)`의 반환 부분을 다시 보면, ```java return fibonacciRecursive(1) + fibonacciRecursive(2); ``` 이제 `fibonacciRecursive(1)`이 호출된다.

이후 `fibonacciRecursive(1)`이 1을 반환하고, `fibonacciRecursive(2)`를 호출한다.

이후, `fibonacciRecursive(2)`가 `fibonacciRecursive(0)` 호출 및 0 반환, `fibonacciRecursive(1)` 호출 및 1 반환된다. 그래서 `fibonacciRecursive(2)`가 반환되고, `fibonacciRecursive(3)`가 반환된다.

그렇게 fibonacciRecursive(4)까지 반환하면서 스택 프레임이 종료된다.

재귀 함수의 장단점#

다음과 같이 계속 호출 및 반환하는 과정만 봐도 성능상 좋지는 못한 걸 알 수 있다. 하지만 읽기 좋은 코드 작성이 기본인 만큼 단편적으로 판단하기는 힘들어 보인다. 그래서 재귀함수의 장단점에 대해 알아보자.

장점#

• 가독성이 좋음
• 코드가 짧음
• 각 단계의 변수 상태가 자동 저장됨(함수의 스택 프레임)
• 코드 검증도 쉬움

단점#

• 재귀적 문제 분석/설계가 직관적이지 않음
• 맹목적인 믿음이 필요
• 스택 오버플로우 발생 가능(재귀 함수 호출이 너무 깊은 경우)
• 함수 호출에 따른 과부하

재귀함수와 반복문 중 어떤 걸 사용해야 할까?#

일단 읽기 좋은 코드 작성이 기본이다. 그래서 기본적으로는 재귀 함수를 사용하는 게 나은 방법이라고 볼 수 있다.(가독성이 좋고 유지보수가 쉬운 코드가 더 중요)

하지만, 다음과 같은 경우에는 반복문으로 변환하는 것이 좋다.

• 스택 오버플로가 날 가능성이 있는 경우
• 성능 문제가 일어날 가능성이 큰 경우
• 성능 문제가 확인된 경우

모든 재귀함수는 반복문으로 작성이 가능하다. 그래서 “변환이 안되면 어떡하지?”와 같은 걱정은 하지 않아도 된다. 하지만 복잡한 경우, 스택 등의 데이터 구조를 사용해야 한다.

NOTE

하지만! 성능 걱정이 없는 재귀함수도 있다.!!

성능 걱정할 필요가 없는 재귀함수에 대해서도 알아보자.

꼬리 호출(tail call)#

꼬리 호출은 함수 코드 제일 마지막에서 다른 함수를 호출하는 경우에 사용한다. 그리고 그 후에 실행하는 명령어가 없다. 코드로 한번 보자.

public int calculateSignature(int[] data, int multiplier) {
    int[] tempData = new int[data.length];
    for (int i = 0; i < data.length; ++i) {
        tempData[i] = data[i] * multiplier;
    }
    return accumulate(tempData);
}

위 코드를 보면 스택 프레임이 두개만 존재한다.

여기서 `calculateSignature()`를 유지할 실익이 있을까? ### 꼬리 호출과 스택 프레임 스택 프레임이 존재하는 이유는 함수에서 사용중인 변수 값을 유지하거나, 타 함수 호출 후 반환되면 스택에 저장했던 값을 되돌려 사용해야 하기 때문이다.

하지만 꼬리 호출의 경우에, 타 함수로부터 반환 후 더 이상 연산이 없다.(곧바로 호출자로 반환된다.) 따라서 스택 프레임에 저장해 놓은 변수 값을 재사용하지 않는다. 그래서 컴파일러가 스택 프레임을 따로 안만드는 최적화를 하기도 한다.

하지만, 이런 최적화를 언어별, 컴파일러별로 지원하거나 안할수도 있다. 그래서 자신이 어떤 언어와 컴파일러를 사용하는지 알아봐야 한다.(자바는 지원 안한다…)

꼬리 재귀#

꼬리 재귀는 꼬리 호출의 특수한 경우이다. 꼬리 재귀는 호출하는 함수(꼬리 호출)이 자기 자신(재귀)인 경우를 말한다. 이 경우, 꼬리 호출과 똑같은 최적화가 적용된다.

팩토리얼 재귀 함수를 통해 이해를 해보자.

팩토리얼 꼬리 재귀 함수#

int factorialRecursive(int n) {
	if (n <= 1) {
		return 1;
	}
	
	return n * factorialRecursive(n - 1);
}

위 함수는 꼬리 재귀가 아니다. 위에서 return시 n이 스택 프레임에서 들고 있다 결과값에 곱해서 반환해야 하기 때문이다. 팩토리얼 꼬리 재귀 함수는 다음과 같다.

int factorial(int n) {
	return factorialRecursive(n, 1);
}

int factorialRecursive(int n, int fac) {
	if (n <= 1) {
		return fac;
	}
	
	return factorialRecursive(n - 1, n * fac); // 이 함수 호출이 마지막 명령어이다.
}

꼬리 재귀 함수#

위 두 코드를 보면, 꼬리 재귀 함수가 더 읽기 힘들다는 것을 체감할 것이다. 보통 꼬리 재귀 함수가 덜 직관적이다. 하지만 최적화를 이유로 위와 같이 작성된 코드가 종종 보일 것이다.

하지만 만약 꼬리 재귀 최적화를 지원하지 않는 언어라면 어떻게 해야 할까? 그냥 재귀함수로 작성해야 할까? 한번쯤은 생각해보는 것이 의미가 있다. 꼬리 재귀는 반복문으로 쉽게 바꿀 수 있기 때문이다.

Footnotes#

1. 이 포스트는 udemy의 자료구조 알고리즘(포프)의 강의를 기반으로 작성되었습니다. ↩