C++로 쉽게 풀어쓴 자료구조/ 순환

순환(Recursion)의 소개

순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. (재귀는 초기항과 수열을 이루는 규칙을 통해 수열을 간결하게 표현할 수 있는 점화식의 개념을 컴퓨터에서 구현한 것과 같다.)

순환 호출의 내부적인 구현

프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일하다. 즉, 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 파라미터와 지역 변수를 스택으로부터 할당 받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드(Activation Record)라고 한다.

이러한 준비가 끝나면 호출된 함수의 코드 시작 위치로 이동하여 수행을 시작한다. 만약 호출된 함수가 자기 자신이라면 자기 자신의 시작 위치로 점프하게 되는 것이다. 혼출된 함수가 끝나게 되면 시스템 스택에서 복귀주소를 꺼내 자신을 호출한 함수로 되돌아간다. 순환 호출이 계속 중첩될 수록 시스템 스택에는 활성 레코드들이 쌓이게 된다.

C, C++, Java, PASCAL 등의 거의 모든 프로그래밍 언어에서 순환을 지원하지만 FORTRAN, COBOL, BASIC에서는 지역변수가 없거나 있더라도 정적으로 할당되므로 순환이 불가능하다. 즉, 함수 호출마다 새로운 지역변수를 만들지 못하면 이전 호출과 구분할 수가 없어서 호출이 불가능하다.

순환 알고리즘의 구조

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

순환 <-> 반복

프로그래밍 언어에서 어떤 일을 되풀이하는 방법에는 반복(iteration)과 순환(recursion)의 2가지가 있다. 반복은 문제를 간결하고 효율적으로 해결할 수 있으며 우리에게 익숙한 방식이다. 반면 어떤 문제들은 반복을 사용하면 지나치게 복잡해지는 경우도 있는데, 이런 경우에는 순환이 좋은 해결책이 될 수 있다. 예컨대 트리 알고리즘으로 트리의 순회나 노드의 삽입과 삭제 등에는 순환이 좋다. 순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 매우 효율적이다.

기본적으로 순환과 반복은 그 표현 능력이 같으며 많은 경우 특히 순환 호출이 끝에서 이뤄지는 순환 알고리즘의 경우는 반복으로 간단히 바꿀 수 있다. 순환은 어떤 문제에 대해서는 반복에 비해 알고리즘을 명확하고 간결하게 나타낼 수 있다는 장점이 있지만, 일반적으로 순환은 함수 호출을 하게 되므로 반복에 비해 수행속도 면에서 떨어진다.

순환의 원리

주어진 문제를 더 작은 동일한 문제들로 분할하여 해결하는 방법을 분할 정복(divide and conquer)라고 한다. 중요한 것은 순환 호출이 일어날 때마다 문제의 크기가 작아진다는 점이다. 문제의 크기가 점점 작아지면 풀기가 쉬워지고 결국은 아주 풀기 쉬운 문제가 된다.

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

순환 알고리즘의 성능

반복 알고리즘과 순환 알고리즘의 시간 복잡도는 동일하다. 그러나 순환 호출의 경우 여분의 기억 공간이 더 필요하고, 또한 함수를 호출하기 위해 함수의 파라미터들을 스택에 저장하는 것과 같은 사전 작업이 상당히 필요하다. 따라서 수행 시간도 더 걸린다.

거듭제곱 값 계산

흔하지는 않지만 순환이 더 빠른 예도 있다. x의 n 제곱을 구하는 함수의 경우 반복을 이용해 구하면 n의 갯수만큼 곱셈이 발생하지만 (O(n)), xn = (x2)n/2의 공식을 이용하여 순환적으로 계산하면 O(log2n)이 되어 더 빠르게 계산할 수 있다. –이 알고리즘의 경우 순환을 돌 때마다 문제의 크기가 하나씩 줄어드는게 아니라 절반씩 줄어든다.

power(x, n)

if n == 0
    return 1;
else if n == 짝수
    return power(x2, n/2);
else if n == 홀수
    return x*power(x2, (n-1)/2);

피보나치수열의 계산

순환을 사용하면 코드를 단순하게 작성할 수 있고 가독성도 높아지지만, 똑같은 계산을 몇 번씩 반복해야 한다면 문제가 있을 수 있다. 대표적인 예가 피보나치 수열인데, 같은 계산을 몇 번씩 반복하기 때문이다.

int fib(int n)
{
    if (n == 0 || n == 1) 
        return n;
    else
        return (fib(n-1)) + fib(n-2));
}

위 그림의 fib(6)을 구하는 과정에서 fib(4)가 2번, fib(3)은 3번 불리고 있다는 것을 볼 수 있다. 이런 문제를 피하기 위해 함수 바깥에 계산 결과를 관리하는 자료형을 두고 한 번 계산된 값은 두 번 계산하지 않게 하는 방법을 사용한다.

하노이 탑 문제

하노이탑 문제는 다음과 같이 해결할 수 있다. n개의 원판이 A에 쌓여 있는 경우, 먼저 위에 쌓여 있는 n-1개의 원판을 B로 옮긴 다음, 제일 밑에 있는 원판을 C로 옮긴다. 그러고나서 B에 있던 n-1개의 원판을 C로 옮긴다.

이 상황에서 n-1개의 원판을 C로 옮기는 것은 n개의 원판을 C로 옮기는 것과 동일한 문제가 된다. 하노이탑에서 원판을 A에서 B로 옮기는 것이나 B에서 C로 옮기는 것등은 모두 동일한 문제이기 때문이다. 전자의 경우 C를 임시로 사용하면 되고, 후자의 경우 A를 임시로 사용하면 된다. 두 경우 모두 바닥에는 움직일 원판 보다 더 큰 원판이 있을 것이므로 문제가 없다.

void hanoiTower(int n, char from, char tmp, char to)
{
    if (n == 1)
        // from 에서 to 로 원판을 옮긴다. 옮기는 코드 생략
    else
        hanoiTower(n-1, from, to, tmp); // from의 맨 밑의 원판을 제외한 나머지 원판들을 tmp로 옮긴다.
        // from에 있는 한 개의 원판을 to로 옮긴다. 옮기는 코드 생략
        hanoiTower(n-1, tmp, from, to); // tmp의 원판들을 to 로 옮긴다.
}

반복적인 형태로 바꾸기 어려운 순환

return n * factorial(n-1); // 꼬리 순환
return factorial(n-1) * n; // 머리 순환

꼬리 순환은 순환 호출이 함수의 맨 끝에서 이루어지는 형태의 순환이다. 꼬리 순환의 경우 알고리즘은 쉽게 반복적인 형태로 변환이 가능하다. 그러나 머리 순환의 경우나 그 외의 여러 군데에서 자기 자신을 호출하는 경우 쉽게 반복적인 코드로 바꿀 수 없다. 만약 꼬리 순환과 머리 순환 양쪽으로 모두 표현할 수 있다면 당연히 꼬리 순환으로 작성해야 한다.

다중 순환

다중 순환이란?

순환 함수들은 호출이 발생할 때마다 몇 개의 순환 호출이 이루어지는가에 따라 선형 순환, 이진 순환, 다중 순환으로 나눌 수 있다.

선형 순환(linear recursion)은 함수의 호출이 발생하면 최대로 하나의 순환 호출이 이루어지는 경우로 팩토리얼이나 거듭제곱 계산이 이에 해당한다.

이진 순환(binary recursion)은 함수에서 두 개의 순환 호출이 발생하는 경우를 말하는데, 피보나치 수열이나 하노이의 탑 문제가 이에 해당한다. 이를 일반화 하여 하나의 함수에서 두 개 이상의 순환 호출이 이루어지는 경우를 다중 순환(multiple recursion)이라고 한다.

영역 채색 문제

영상 처리 분야에서 영역 채색(blob coloring) 또는 연결 화소 분석법(connected component labelling)이라 불리는 알고리즘은 흑과 백의 화소 값만을 갖는 이진 영상에서 연결된 객체를 찾는 방법으로 영상처리에서 매우 중요한 연산의 하나 이다.

순환 기법을 사용하면 영역 채색 문제를 간단하게 구현할 수 있다. 먼저 이진 영상을 스캔하다가 흰 화소를 만나면 어떤 색으로 칠한다. 그리고 이 화소와 인접한 네 방향의 이웃 화소에 대해 순환적으로 검사하면서 같은 색으로 칠한다. 즉, 네 방향으로 순환 호출하는 다중 호출의 사례이다.

[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기