[CS과목/자료구조] 02 순환

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)

 

2.1 순환의 소개

 순환(recursion)이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다.

순환 호출의 내부적인 구현
 순환을 이해하기 위하여 먼저 함수 호출의 과정을 살펴보자. 프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다름 함수를 호출하는 것과 동일하다. 즉 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record)라고 한다.

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

순환 vs 반복
 반복이란 for나 while 등의 반복구조로 되풀이 하는 방법이다. 반복을 사용하게 되면 지나치게 복잡해지는 문제들이 존재한다. 이런 경우에는 순환이 좋은 해결책이 될 수 있다.

순환의 원리
 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법을 분할정복(divide and conquer)이라 한다. 여기서 중요한 것은 순환 호출이 일어날 때마다 문제의 크기가 작아진다는 것이다.

순환 알고리즘의 성능
 팩토리얼 예에서 반복 알고리즘과 순환 알고리즘의 성능을 분석하여 보자. 반복 알고리즘은 for를 사용하여 n번 반복하므로 시간 복잡도는 O(n)이다. 순환 알고리즘 역시 O(n)이다. 하지만 순환 호출의 경우 여분의 기억공간이 더 필요하고 또한 함수를 호출하기 위해서는, 함수의 매개변수들을 스택에 저장하는 것과 같은 사전작업이 상당이 필요하다. 따라서 수행시간도 더 걸린다.

#include <stdio.h>

int factorial(int n);

int main()
{
    int n, ans;

    n = 5;
    ans = factorial(n);

    printf("factorial(%d) = %d", n, ans);

    return 0;
}

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

 

2.2 거듭제곱값 계산

 다음은 순환의 개념을 사용하여 n 제곱거듭값인 $x^n$을 구하는 알고리즘을 살펴보자. 이때 반복적인 프로그램과 순환적인 프로그램의 시간복잡도를 비교해보면 반복 알고리즘은 O(n)인 반면 순환 알고리즘은 O($\log n$)이 된다.

#include <stdio.h>

double power(double x, int n);

int main()
{
    int n;
    double x, ans;

    x = 2.0;
    n = 5;
    ans = power(x, n);

    printf("power(%.1f, %d) = %.1f", x, n, ans);

    return 0;
}

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);
}

 

2.4 하노이탑 문제

 순환의 파워를 가장 극명하게 보여주는 예제가 바로 이절에 다룰 하노이탑 문제이다. 주어진 문제를 이해하기 위하여 원판의 개수가 3개인 경우를 살펴보자. 문제는 막대 A에 쌓여있는 원판 3개를 막대 C로 옮기는 것이다. 단 다음의 조건을 지켜야 한다.

• 한 번에 하나의 원판만 이동할 수 있다.
• 맨 위에 있는 원판만 이동할 수 있다.
• 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.
• 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.

 이 문제는 순환적으로 생각하면 쉽게 해결할 수 있다. 순환이 일어날수록 문제의 크기가 작아져야 한다. 다음과 같이 문제를 나누어 생각하여 보자. n개의 원판이 A에 쌓여있는 경우, 먼저 위에 쌓여 있는 n-1개의 원판을 B로 옮긴 다음, 제일 밑에 있는 원판을 C로 옮긴다. 이어서 B에 있던 n-1개의 원판을 C로 옮긴다. 자 이제 문제는 B에 쌓여있던 n-1개의 원판을 어떻게 C로 옮기느냐이다. 이 문제를 다음과 같이 알고리즘을 이용하여 해결할 수 있다.

#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to);

int main(void)
{
	hanoi_tower(4, 'A', 'B', 'C');

	return 0;
}

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", n, from, to);
		hanoi_tower(n - 1, tmp, from, to);
	}
}