재귀 (Recursion)

재귀 또는 순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 재귀는 많은 문제들을 해결하는데 독특한 개념적인 해결책을 제공한다.

 

재귀를 이용하여 만든 재귀 함수는 어떻게 문제를 풀어가는지에 대해 직관적으로 알 수 있도록 해주어 가독성을 높인다는 장점이 있다.

 

하지만 단점도 존재한다. 함수를 호출하면 그 함수가 끝날때 어디로 복귀해야 한다는 복귀주소를 스택에 쌓게 되는데, 재귀함수는 재귀하는 횟수가 많아 질수록 이 쌓이는 복귀주소가 기하급수적으로 늘어나게 된다. 이로인해 스택 오버플로우가 발생하면 프로그램이 뻗는 현상이 나타난다. (이를 해결하기 위해 동적 계획법(Dynamic Programming)이라는 알고리즘을 사용한다)

 

재귀는 트리 구조에서 정말 많이 사용한다. 그래서 재귀를 알아야 트리 구조를 이해할 수 있다. 

 

재귀란?

재귀는 본질적으로 재귀적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다. 예를 들어 정수의 팩토리얼(Factorial)은 다음과 같이 정의한다.

 

위의 정의에서 팩토리얼 n!을 정의하는데 다시 팩토리얼 (n - 1)!이 사용된 것에 주목하자. 이러한 정의를 재귀적이라 한다. 위의 정의에 따라 n!을 구하는 함수 Factorial(n)을 구현해보자. n!을 계산하려면 먼저 (n - 1)!을 구하고 여기에 n을 곱하면 된다. 그러면 (n - 1)!은 어떻게 계산할 것인가? 일단 (n - 1)!을 계산하는 함수 Factorial_n_1()을 따로 만들어 호출해보자.

int Factorial(int n)
{
	if(1 == n) 
		return 1;	// n == 1인 경우
	else
		return ( n * Factorial_n_1(n-1) ); // n > 1 인 경우
}

그런데 이 함수의 매개변수를 자세히 살펴보면 정수 n을 받아 n!을 구하는 함수이다. 그렇다면 (n - 1)!을 구하기 위해 이 함수를 그대로 사용하고, 매개변수만 (n - 1)으로 바꾸면 되지 않을까? 이것이 가능하다면 Factorial_n_1()을 따로 만들 필요가 없다. 이를 바탕으로 함수를 다시 만들면 다음과 같다.

int Factorial(int n)
{
	if (1 == n)
		return 1;	// n == 1인 경우 (종료 조건)
	else
		return (n * Factorial(n - 1)); // n > 1인 경우 (순환 조건)
}

 팩토리얼의 재귀적인 특성을 이용하여 재귀함수를 하나 만들었다. 신기하게도 위 함수는 잘 돌아간다.

 

Factorial(3)을 호출하면 다음과 같이 동작한다.

 

 여기서 주의할 점은 종료 조건이 들어가 있다는 것이다. 종료 조건이 없으면 재귀 함수는 무한히 재귀하게 된다. 재귀함수가 제대로 작동하도록 하기 위해서는 반드시 종료 조건을 넣어줘야 한다. 

 

재귀호출의 내부적인 구현

앞에서 간략하게 설명했지만, 컴퓨터가 어떻게 처리하는지 좀 더 자세하게 알아보도록 하겠다. 먼저 함수의 호출 과정을 살펴보자. 컴퓨터에서 어떤 함수가 다른 함수를 호출하나 자기 자신을 호출하나 전혀 차이가 없다. A라는 함수에서 함수 B가 호출되면, 먼저 B가 끝나고 A의 처리 상황을 복원할 수 있도록 A의 복귀 주소와 사용하던 지역 변수 등의 자료를 모아 활성 레코드(Activation record)를 준비하고 이를 시스템 스택에 저장한다. 이런 준비가 끝나면 B의 코드 시작 위치로 이동하여 처리를 시작한다. (만약 A가 자기 자신을 호출했다면 A의 코드 시작 위치로 이동한다) 호출된 함수 B가 끝나면 스택에서 복귀주소를 꺼내 자신을 호출한 함수 A로 되돌아간다. 순환호출이 중첩될수록 스택에는 활성 레코드들이 쌓이게 된다.

 

이런 식으로 시스템 스택에 쌓이고

이런 식으로 시스템 스택에서 꺼내 복귀한다.

 

재귀 알고리즘 구조

재귀 알고리즘은 자기 자신을 재귀적으로 호출하는 부분과 재귀 호출을 멈추는 부분으로 구성되어 있다. 앞서 설명했지만, 만약 순환 호출을 멈추는 부분이 없다면 시스템 스택을 다 사용할 때까지 순환적으로 호출되다가 결국 오류를 내면서 멈출 것이다. 

int Factorial(int n)
{
	cout << "Factorial(" << n << ")\n";
	return n * Factorial(n - 1);
}

팩토리얼 재귀함수에 종료 조건을 빼보고 실행을 해보면 다음과 같다.

 

요즘 컴파일러는 많이 똑똑해져서 종료조건이 없는 재귀함수에 대해서 컴파일 시점에서 경고한다.

Factorial(100000)을 호출하였을때 처리하다 중간에 프로그램이 뻗어 강제 종료되었다. 따라서 순환호출에는 순환 호출을 종료하는 코드가 반드시 포함되어 있어야 한다.

 

재귀? 반복?

같은 일을 되풀이 할때에는 반복을 사용한다. for나 while등의 반복문을 사용하는 것으로 반복횟수를 가지고 있는 변수를 사용하여 일정횟수동안이나 어떤 조건이 만족될 때 까지 반복하도록 했다. 이러한 반복 구조는 문제를 간결하고 효율적으로 해결할 수 있다.

 

그러나 어떤 문제들은 반복을 사용하면 지나치게 복잡해지는 경우도 있다. 이런 경우에는 재귀가 매우 좋은 해결책이 될 수 있다. 예를 들면 트리 알고리즘을 들 수 있다. 트리의 순회나 노드의 삽입연산 등 재귀가 많이 사용되는데, 이들을 반복으로 구현하면 코드가 매우 복잡해진다. 따라서 재귀는 재귀적인 문제나 그러한 자료구조를 다루는 프로그램에 매우 효율적이다.

 

팩토리얼 재귀 함수를 반복문으로 표현하면 다음과 같다.

int Factorial(int n)
{
	int result = 1;
	for (int i = n; i > 0; --i)
	{
		result = result * i;
	}
	return result;
}

 

분할정복(Divide and conquer)

팩토리얼의 재귀호출 함수를 보면 문제를 전혀 해결하지 않고 재귀호출만 하는 것은 아니다. 전체 문제의 일부만을 먼저 해결한 다음, 재귀 호출을 한다.

int Factorial(int n)
{
	if (1 == n)
		return 1;
	else
		// n : 해결된 부분
		// Factorial(n - 1) : 남아있는 부분
		return (n * Factorial(n - 1)); 

}

일부가 해결되면 남은 문제는 원래의 문제보다 쉬워진다. 더 쉬워진 문제도 동일한 방법으로 처리한다. 이런 식으로 어떤 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법을 분할정복이라고 한다. 재귀호출이 일어날 때마다 문제의 크기가 반드시 작아져야 한다. 문제의 크기가 점점 작아지면 풀기 쉬워지고 결국은 풀기 쉬운 문제가 된다.

 

재귀 알고리즘의 성능

팩토리얼을 예로들어 반복과 재귀의 성능을 알아보자. 팩토리얼 반복 알고리즘의 시간 복잡도는 for를 사용하여 n번 반복하므로 시간 복잡도는 O(n)이다. 팩토리얼 재귀 알고리즘의 시간 복잡도는 어떻게 될까? 곱셈의 횟수로 생각해 보자. 재귀에서는 한번 호출할 때마다 1번의 곱셈이 수행되고 전체 재귀 호출이 n번 일어나므로 역시 O(n)이다. 

 

이 문제에서 반복 알고리즘과 재귀 알고리즘의 시간 복잡도는 같다. 재귀 호출의 경우 내부적으로 기억공간을 더 사용할 것이고, 실제 실행시간도 더 길다. 결국 재귀 알고리즘은 이해하기 쉽다는 것과 쉽게 프로그램 할 수 있다는 장점이 있는 대신 수행 시간과 기억 공간의 사용에 있어서는 비효율적인 경우가 많다.

 

---

재귀 알고리즘 예

피보나치수열

피보나치수열은 다음과 같이 재귀적으로 정의된다.

 

 일반적인 경우, 앞의 두 개의 숫자를 더해서 뒤의 숫자를 만들어 낸다. 정의에 따라 수열을 차례대로 만들어 보면 다음과 같다.

 

피보나치수열은 정의 자체가 재귀적이다. 따라서 재귀 호출을 사용하여 구현하는 것이 자연스럽다. 위 정의를 이용하여 피보나치 수열을 구하는 재귀함수를 구현하면 다음과 같다.

int Fibonacci(int n)
{
	if (0 == n)
		return 0;
	if (1 == n)
		return 1;
	return Fibonacci(n - 1) + Fibonacci(n - 2);
}

이 함수는 단순하고 이해하기 쉽게 구현되었지만 매우 비효율적이다. 왜 그럴까? 그림을 먼저 살펴보자. 

Fibonacci()를 줄여 f()로 가정한다.

f(6)을 호출하면 f(4)가 두 번 반복하여 호출된다. f(3)은 3번 호출되고 이런 현상은 재귀호출이 깊어 질수록 점점 심해진다. f(6)을 구하기 위해 f()함수가 총 25번이나 재귀호출된 것에 유의하자. 

 

근본적인 이유는 중간에 계산되었던 값을 기억하지 않고 다시 계산하기 때문이다. n이 작을 때는 중복계산이 비교적 적지만 n이 커지게 되면 엄청난 순환호출이 필요하게 된다. 예를 들어 n이 25이면 25만 번의 호출을 해야 하고 n이 30이면 약 300만 번의 함수 호출이 필요하다. 따라서 n이 커지면 재귀호출을 사용하여 피보나치수열을 계산하는 것이 거의 불가능해진다.

 

이럴 경우에는 반복 구조가 훨씬 효율적이다.

int Fibonacci(int n)
{
	if (n < 2) 
		return n;
	else
	{
		int last = 0;
		int current = 1;
		for (int i = 2; i <= n; ++i)
		{
			int tmp = current;
			current += last;
			last = tmp;
		}
		return current;
	}
}

혹은 계산된 값을 배열에 기록하여 기록된 정보를 활용하는 동적계획법을 사용하기도 한다. 

https://lipcoder.tistory.com/49?category=843242

동적계획법(Dynamic Programming)

 

 

하노이탑

재귀의 힘을 가장 극명하게 보여는 예가 하노이 탑 문제이다. 주어진 문제를 이해하기 위하여 원판의 개수가 3개인 경우를 살펴보자. 

 

문제는 막대 A에 쌓여있는 원판 3개를 막대 C로 옮기는 것이다. 단, 다음 조건을 지켜야 한다.

 

• 한 번의 하나의 원판만 이동할 수 있다.

• 맨 위의 있는 원판만 이동이 가능하다.

• 크기가 작은 원판위에 큰 원판이 쌓일 수 없다.

• 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.

위의 예를 풀어보면 다음과 같다.

 

4개의 원판이 있는 경우에는 더 복잡해진다. 일반적으로 n개의 원판이 있는 경우를 해결하려면 상당히 복잡해질 것이다.

 

이 문제를 재귀적으로 해결해 보자. 재귀 알고리즘에서는 재귀가 일어날수록 문제의 크기가 작아져야 한다. 이때 문제의 크기는 이동하는 디스크의 갯수가 될 것이다. 다음 그림을 보고 문제를 나누어 생각해보자.

먼저 위에 쌓여 있는 n - 1개의 원판을 B로 옮긴 다음, 제일 밑에 있는 원판을 C로 옮긴다. 그러고 나서 B에 있던 n - 1개의 원판을 C로 옮긴다. 이제 n - 1개의 원판을 옮길 수만 있으면 문제는 해결된다. 

 

n - 1개의 원판을 A에서 B로 옮기나 B에서 C로 옮기나 문제는 동일하다. 전자의 경우 C를 임시로 사용하면 되고, 후자의 경우 A가 임시로 사용된다. 이를 코드로 나타내면 다음과 같다.

void Hanoi(int n, char from, char tmp, char to)
{
	// 1이면 맨 꼭대기 원판이므로 어딜 옮기는 조건이 모두 만족한다.
	if (1 == n)
		cout << "원판 " << n << "을 " << from << "에서 " << to << "으로 옮긴다.\n";
	else
	{
		// n - 1개의 원판을 현재 막대(A)에서 임시 막대(C)를 이용하여 이동하려는 막대(B)로 옮긴다.
		Hanoi(n - 1, from, to, tmp);
		// n 원판을 현재 막대에서 이동하려는 막대로 옮긴다.
		cout << "원판 " << n << "을 " << from << "에서 " << to << "으로 옮긴다.\n";
		// n - 1개의 원판을 현재 막대(B)에서 임시 막대(A)를 이용하여 이동하려는 막대(C)로 옮긴다.
		Hanoi(n - 1, tmp, from, to);
	}
}

 

4개의 원판을 A, B, C 막대에서 옮기는 작업의 출력 값은 다음과 같다.