[자료구조 알고리즘] 순환(재귀)

순환(재귀)

순환이란?

순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.

예) 팩토리얼

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

 

순환 호출의 내부적인 구현

프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일하다. 즉 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record)라 한다. 이러한 준비가 끝나면 호출된 함수의 시작 위치로 점프하여 수행을 시작한다. 만약 호출된 함수가 자기 자신이라면 자기 자신의 시작 위치로 점프하게 되는 것이다. 호출된 함수가 끝나게 되면 시스템 스택에서 복귀주소를 호출하여 호출한 함수로 되돌아가게 된다. 순환호출이 계속 중첩될수록 시스템 스택에는 활성 레코드들이 쌓이게 된다.

 

순환 알고리즘의 구조

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

int factorial(int n)
{
    if( n <= 1 ) return(1);				// -> 순환을 멈추는 부분
    else return (n * factorial(n-1));	// -> 순환 호출을 하는 부분
}

 

순환 <-> 반복

프로그래밍 언어에서 되풀이하는 방법에는 반복(iteration)과 순환(recursion)의 2가지가 있다.

반복이란 for나 while등의 반복구조로 되풀이 하는 방법이다. 때로는 반복을 사용하게 되면 지나치게 복잡해지는 문제들도 존재한다. 이런 경우에는 순환이 좋은 해결책이 될 수 있다. 순환은 본질적으로 순환적(recursive)인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다.

기본적으로 반복과 순환은 문제 해결 능력이 같으며 많은 경우에 순환 알고리즘을 반복 버전으로, 반복 알고리즘을 순환 버전으로 바꾸어 쓸 수 있다. 특히 순환 호출이 끝에서 이루어지는 순환을 꼬리 순환(tail recursion)이라 하는데, 이를 반복 알고리즘으로 쉽게 바꾸어 쓸 수 있다.

그러나 일반적으로 순환은 함수 호출을 하게 되므로 반복에 비해 수행속도 면에서는 떨어진다. 따라서 알고리즘을 설명할 때는 순환으로 하고 실제 프로그램에서는 그것을 반복 버전으로 바꾸어 코딩하는 경우도 있다. 물론 순환이 더 빠른 예제도 존재한다.

// 반복 팩토리얼
int factorial_iter(int n)
{
	int i, result = 1;
	for (i = 1; i <= n; i++)
		result = result * i;
	return(result);
}

 

순환의 원리

순환적인 팩토리얼 함수를 살펴보면, 문제를 하나도 해결하지 않고 순환호출만 하고 있는 것은 절대 아니다. 문제의 일부를 해결한 다음, 나머지 문제에 대하여 순환 호출을 한다는 것을 유의하여야 한다.

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

순환은 알고리즘의 정의가 순환적으로 되어 있는 경우에 유리한 방법이다. 예를 들어 팩토리얼 함수 계산, 피보나치 수열, 이항계수 계산, 이진 트리 알고리즘, 이진 탐색, 하노이 탑 문제들은 순환 알고리즘을 쓰는 것이 자연스러운 알고리즘들이다.

 

순환 알고리즘의 성능

팩토리얼 함수의 순환 알고리즘과 반복 알고리즘의 성능을 분석해보자. 반복 알고리즘의 시간 복잡도는 어떻게 될까? for를 사용하여 n 반복하므로 시간 복잡도는 O(n)이다. 팩토리얼의 순환 알고리즘 구현의 시간 복잡도는 어떻게 될까? 즉 곱셈이 몇 번이나 반복되는 것일까? 한번 순환 호출할 때마다 1번의 곱셈이 수행되고 순환 호출은 n이 일어나므로 역시 O(n)이다. 반복 알고리즘과 순환 알고리즘이 시간 복잡도는 같지만 순환 호출의 경우 여분의 기억공간이 더 필요하고 또한 함수를 호출하기 위해서는, 함수의 매개변수들을 스택에 저장하는 것과 같은 사전 작업이 상당히 필요하다. 따라서 수행시간도 더 걸린다. 결론적으로 순환 알고리즘은 이해하기 쉽다는 것과 쉽게 프로그램할 수 있다는 장점이 있는 대신 수행 시간과 기억 공간의 사용에 있어서는 비효율적인 경우가 많다. 순환 호출시에는 호출이 일어날 때마다 호출하는 함수의 상태를 기억되어야 하므로 여분의 기억장소가 필요한 것이다.

 

 

참고

• C언어로 쉽게 풀어쓴 자료구조 책