[자료구조] 순환(Recursion) with C

순환 

---

순환 (재귀) - 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법

예) 팩토리얼 값 구하기, 피보나치수열, 하노이 탑 등... 

순환호출을 사용하여 factorial 구하기

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

 

만약 factorial(5)를 순환호출을 이용하여 구한다고 하면, 다음과 같이 나타 낼 수 있습니다.

순환 알고리즘의 구조 

순환 알고리즘은 다음과 같은 부분을 포함해야 합니다.

• 순환 호출을 하는 부분

• 순환 호출을 멈추는 부분

만약 순환 호출을 멈추는 부분이 없다면? -> 무한정 호출, 프로그램이 종료되지 않음

 

순환(recursion)과 반복(iteration)의 차이

• 순환 - 순환 호출 이용, 순환적인 문제에 자연스러움, 함수 호출의 오버헤드 발생 가능성

• 반복 - 수행속도가 빠름, 순환적인 문제에 대해서 프로그램 작성이 어려움

모든 순환은 반복으로 바꾸어 작성이 가능합니다 But!!, 매우 불편하거나 어려운 경우가 많습니다. ㅎ 

 

순환(recursion)의 작동 원리

 

순환호출의 경우 복귀 주소를 시스템 스택에 저장하고, 호출할 함수를 위한 파라미터와 지역변수를 스택으로부터 할당받게 됩니다.  

이러한 순환의 작동 원리 때문에 반복에 비해 메모리 할당이 비효율적이며, 수행 시간도 나쁩니다.

 

순환 호출을 사용하면 효율적인 예로는 거듭제곱 값 구하기, 팩토리얼, 하노이탑 문제 등이 있고

반복을 사용하면 효율적인 예로는 피보나치 수열이 있습니다. 

 

1. 거듭제곱(x^n)

반복을 사용 하였을 경우 (비효율적인 방법)

double slow_power(double x, int n) {
    int i;
    double r = 1.0;
    for(i=0; i <n; i++){
        r = r*x;
    }
    return r;
}

 

순환을 사용 하였을 경우 (효율적인 방법)

double power(double x, int n) {
    if (n == 0) {
        return 1;
    } else if (n % 2 == 1) {
        return x*power(x*x, (n-1)/2);
    } else {
        return power(x*x, n/2);
    }
}

 

실제로 반복을 사용한 경우와 순환을 사용한 경우에 대하여 수행 시간 측정을 해보면 순환을 사용한 경우가 더 빠른 것 을 알 수 있습니다.

제 컴퓨터 기준 x = 5, n = 100을 대입했을 때, 반복은 0.00016초가 소요되고, 순환은 0.000008초가 소요되네요. 위에서는 반복이 순환보다 수행 속도가 더 빠르다고 적었는데 왜, 거듭제곱의 경우 순환호출을 사용하였을 때 더 빠를까요? 

반복과 순환호출의 내부를 들여다보면 그 답이 나옵니다! 

반복을 사용할 경우 n 이 1000일 때 1000번의 연산이 필요하지만, 순환호출의 경우 11번의 연산(호출)만을 필요로 합니다. 정말 엄청난 차이죠?? 

각각의 시간 복잡도를 빅오 표기법으로 표현하면, 

반복을 사용했을 경우: O(n)

순환을 사용 했을 경우: O(logn)

이 되게 됩니다.

 

2. 피보나치 수

순환을 사용하였을 경우 (비효율적인 방법)

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

 

반복을 사용 하였을 경우 (효율적인 방법)

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

 

피보나치 수의 경우 거듭제곱을 구하는 것과는 다르게, 순환호출보다 반복을 사용하는 것이 더 좋습니다.

즉, 피보나치수열의 경우 순환호출을 사용하면 비효율 적인데요. 왜 비효율 적일까요? 이 또한 내부를 살펴보면 알 수 있습니다. ㅎㅎ 

만약 fib(6)을 순환호출로 구한다고 하면, 다음과 같이 나타낼 수 있습니다.

순환호출 과정에서, 불가피하게 fib(3)과 fib(2)등을 여러번 호출 하는 것을 볼 수 있습니다. 순환호출 과정 상 어쩔 수 없지만, 같은 항이 중복 계산됨에 따라, n이 커질수록 이렇게 중복 계산되는 항은 더 많아지고 이에 따라 비효율성은 점점 더 커지게 됩니다.  

 

3. 하노이 탑

마지막으로, 알고리즘의 기초적인 문제지만, 생각보다 이해하기 까다로운(?) 하노이탑 문제입니다. (하노이탑 게임의 경우 이 링크를 통해 직접 해 보실 수 있습니다.)

하노이탑 규칙

• 한 번에 하나의 원판만 이동 가능
• 맨 위에 있는 원판만 이동 가능 
• 큰 원판이 작은 원판 위에 있어서 안됨

만약 원판이 3개라면, 아래와 같이 7번을 움직여 탑을 만드는 것이 가장 적은 횟수로 만드는 방법이 됩니다.

그럼, 순환호출을 사용하여 하노이탑 프로그램을 코드로 작성해 볼까요??

우선 무작정, 코드를 짜기보다, 생각을 해야 합니다. (생각보다 어렵거든요 ㅋㅋ)

우리의 전략은 이렇습니다.

1. 가장 큰 원판을 C로 옮기기 위해 C를 임시 버퍼(보조기둥)로 사용하여 나머지 원판을 B로 옮깁니다. 

2. A에 있던 가장 큰 원판을 C로 옮긴 후 A를 임시버퍼(보조기둥)로 사용하여 B에 있는 나머지 원판을 C로 옮깁니다.

여기서 나머지 원판을 옮기는 방법에 대해서 구체적으로 명시하지 않았는데, 어떻게 옮기라는 말일까요? 

방법은 순환호출(재귀호출) 입니다! ㅎ 

우리는 하노이탑 함수의 입력 변수로 원판의 개수 n과, 첫 번째 기둥, 두 번째 기둥, 세 번째 기둥을 받을 겁니다.

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

만약 n = 3이라면, 다음과 같이 함수의 호출이 일어나게 됩니다. (작은 원판 부터 큰 원판 순으로 번호를 매겼습니다.)

1. 1번과 2번 원판을 임시 버퍼인 B로 옮기고

2. 3번 원판을 C로 옮깁니다. 

3. 나머지 B에 있던 원판을 C로 옮깁니다.

위의 전략 그대로죠? 하지만, 말이 쉽지 정말 무에서 재귀호출을 사용하여 하노이탑 문제를 푼다는 것은 쉽지 않습니다. 

하노이탑과 관련 글 들을 읽어보던 중 하노이탑 재귀호출까지 도달하는 논리적인 과정을 잘 풀어서 작성한 좋은 글이 있기에 여기에 첨부합니다. 만약 하노이탑 문제풀이를 도출하기까지 생각하는 과정(?), 방법(?)을 알고 싶으신 분들은 이 글을 참고해 주세요! 

마지막으로 하노이탑의 시간 복잡도의 경우

n = 2일 경우,  3

n = 3일 경우,  7

n = 4일 경우, 15로

f(n) = 2^n - 1, = O(2^n)이 되게 됩니다.

 

이것으로 순환(재귀)에 대한 정리를 마치겠습니다.

읽어주셔서 감사합니다 :)