재귀
재귀(순환, recursion)란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.
1. 재귀의 구조 및 구현
프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일하다. 즉 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수와 지역변수를 스택으로부터 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record)라 한다. 따라서 재귀 호출이 중첩될수록 시스템 스택에는 활성 레코드들이 쌓이게된다.
재귀 알고리즘은 자기 자신을 순환적으로 호출하는 부분과 순환 호출을 멈추는 부분으로 구성되어 있다. 만약 순환 호출을 멈추는 부분이 없다면 시스템 스택을 다 사용할 때까지 순환적으로 호출되다가 결국 오류를 내면서 멈출 것이다.
2. 재귀 vs 반복
되풀이하는 것은 많은 컴퓨터 알고리즘에서 볼 수 있는 주요한 특징이다. 프로그래밍 언어에서 되풀이하는 방법은 반복(iteration)과 재귀(recursion) 2가지가 있다.
반복이란 for문이나 while문 등의 반복구조로 되풀이하는 방법이다. 이러한 반복은 간명하고 효출적으로 되풀이를 구현하는 방법이다. 하지만 때로는 반복을 사용하게 되면 지나치게 복잡해지는 문제들도 존재한다. 이런 경우에는 재귀가 해결책이 될 수 있다. 재귀는 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다.
기본적으로 반복과 재귀는 문제 해결 능력이 같으며 많은 경우에 재귀 알고리즘을 반복 버전으로, 반복 알고리즘을 재귀 버전으로 바꾸어 쓸 수 있다. 특히 순환 호출이 끝에서 이루어지는 것을 꼬리 순환(tail recursion)이라 하는데, 이는 반복 알고리즘으로 쉽게 바꾸어 쓸 수 있다. 그러나 재귀는 어떤 문제에서는 반복에 비해 알고리즘이 훨씬 명확하고 간결하게 나타낼 수 있다는 장점이 있다. 그러나 일반적으로 재귀는 함수 호출을 하게 되므로 반복에 비해 수행속도 면에서는 떨어진다. 하지만 적지 않은 경우에 재귀를 사용하지 않으면 구현할 수 없는 경우가 종종 있기 때문에 재귀는 반드시 익혀두어야 한다.
3. 재귀의 원리
재귀는 분할정복(divide and conquer) 방법을 통해 문제를 해결한다. 분할정복은 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법이다. 재귀의 호출이 일어날 때마다 문제의 크기는 작아지고 문제의 크기가 작아지면 풀기가 쉬워지고 결국은 아주 풀기 쉬운 문제가 된다.
재귀는 알고리즘 정의가 순환적으로 되어 있는 경우에 유리한 방법이다. 예를 들어 팩토리얼, 피보나치 수열, 이항계수, 이진 트리 알고리즘, 이진 탐색, 하노이 탑 문제들은 재귀 알고리즘을 쓰는 것이 자연스럽다. 많은 복잡한 알고리즘들이 재귀를 사용하면 간단하게 구현할 수 있다.
4. 재귀 알고리즘의 성능 및 예제
4-1. 팩토리얼
재귀를 사용한 팩토리얼 계산
int factorial(int n)
{
if (n <= 1)
return 1;
else
return (n * factorial(n - 1));
}반복을 사용한 팩토리얼 계산
int factorial(int n)
{
int result = 1;
for (int i = 1; i <= n; i++)
result *= i;
return result;
}위와 같이 팩토리얼을 반복과 재귀로 구현한다고 가정했을 때, 시간 복잡도는 둘 다 동일하게 𝑂(𝑛)이다. 하지만 재귀는 반복보다 여분의 기억공간이 더 필요하고(재귀 함수의 호출이 일어날 때마다 호출하는 함수의 상태를 기억해야하기 때문) 함수를 호출하기 때문에 매개변수들을 스택에 저장하는 등의 사전 작업이 필요하다. 따라서 수행시간도 더 걸린다. 이렇듯 팩토리얼 계산은 반복적인 방법이 재귀에 비하여 속도가 빠르다. 결론적으로 재귀는 이해하기 쉽다는 것과 쉽게 구현할 수 있다(가독성이 높아짐)는 장점이 있는 대신 수행 시간과 기억 공간의 사용에 있어서는 비효율적인 경우가 많다.
4-2. 거듭제곱값 계산
재귀를 사용한 거듭제곱 계산
double power(double x, int n)
{
if (n == 0)
return 1;
else if ((n % 2) == 0)
return power(x * x, n / 2);
else
return x * power(x * x, (n - 1) / 2);
}반복을 사용한 거듭제곱 계산
double slow_power(double x, int n)
{
int i;
double result = 1.0;
for (i = 0; i < n; i++)
result *= x;
return result;
}반면, 거듭제곱값을 계산하는 경우에는 재귀로 구현한 것이 반복으로 구현한 것보다 빠르다. 반복을 사용한 함수는 n만큼의 루프를 돌아야 하기 때문에 시간 복잡도가 𝑂(𝑛)이 되지만 재귀를 사용하면 한 번의 재귀 호출을 할 때마다 문제의 크기는 약 절반으로 줄어들게 되므로 시간 복잡도는 𝑂(log2n)이 된다.
4-3. 피보나치 수열
재귀를 사용한 피보나치 수열 계산
int fib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}반복을 사용한 피보나치 수열 계산
int fib_iter(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
for (int i = 2; i <= n; i++)
{
result = p + pp;
pp = p;
p = result;
}
return result;
}재귀를 이용한 피보나치 수열 계산은 매우 단순하고 이해하기 쉽지만 비효율적이다. 중간에 계산되었던 값을 기억하지 않고 중복으로 다시 계산을 해야하기 때문이다. 시간 복잡도를 계산해보면 상한 𝑂(2^𝑛)을 가지는 상당히 비효율적인 값이 나온다. 이런 경우는 시간 복잡도 𝑂(𝑛)을 가지는 반복 구조를 이용하는 것이 더 효율적이다.
5. 하노이 탑
재귀의 파워를 가장 극명하게 보여주는 예제가 바로 하노이 탑 문제이다. 하노이 탑 문제의 조건은 다음과 같다.
- 한 번에 하나의 원판만 이동할 수 있다.
- 맨 위에 있는 원판만 이동할 수 있다.
- 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.
- 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.
이는 재귀적으로 생각하면 쉽게 해결할 수 있다. 재귀가 일어날 수록 문제의 크기가 작아져야 하고 여기서 문제의 크기는 이동하여야 하는 디스크의 개수가 된다.
재귀를 사용한 하노이 탑
void hanoi_tower(int n, char from, char tmp, char to)
{
if (n == 1)
printf("원판 1을 %c에서 %c으로 옮긴다.\n", from, to);
else
{
hanoi_tower(n - 1, from, to, tmp);
printf("원판 %d을 %c에서 %c으로 옮긴다.\n", from, to);
hanoi_tower(n - 1, tmp, from, to);
}
}
6. 반복으로 바꾸기 힘든 재귀
① return n * factorial(n - 1);
② return factorial(n - 1) * n;위의 팩토리얼 예제 중 ①은 재귀가 함수 맨 끝에서 이루어지는 꼬리 순환(tail recursion)이다. 꼬리 순환의 경우, 쉽게 반복의 형태로 변환이 가능하다.
하지만 ②과 같이 머리 순환(head recursion)의 경우나 하노이 탑 문제처럼 여러 군데에서 재귀가 이루어지는 경우(multi recursion)는 쉽게 반복의 형태로 변환할 수 없다.
만약 동일한 알고리즘을 꼬리 순환과 머리 순환 양쪽으로 표현할 수 있다면 당연히 꼬리 순환으로 작성하는 것이 좋다.
References
