1. 순환(Recursion)

▣ 자료구조의 정의와 순환

자료구조(data structure)에 웬 순환? 이라고 생각할 수 있습니다. 하지만 순환은 단순 반복(iteration)으로 해결하기 복잡하기 어렵거나 시간 복잡도가 매우 큰 문제들을 해결하는데 사용될 뿐만 아니라 추후에 포스팅할 트리 순회(Tree traverse), 이진 탐색, 정렬 알고리즘 등에 사용되므로 알아두는 것이 좋습니다.

 

■ 자료구조(Data Structure)

- 효율적으로 자료에 접근(access)하기 위하여 자료를 조직화하고, 관리하고, 저장하는 방법론입니다.

 

■ 순환(Recursion)

- 어떤 것을 정의할 때 자기 자신의 정의를 사용하여 정의하는 방법입니다. 컴퓨터 과학에서 어떤 문제를 정의하거나 해결하기 위하여 많이 사용됩니다. 다른 말로 재귀호출이라고도 합니다.

 

■ 순환을 이용한 정의는 base case와 induction step으로 구성됩니다.

- Base case : 순환을 사용하지 않고 정의.

- Induction step : 순환을 사용하여 정의.

 

■ 팩토리얼의 정의는 다음과 같습니다.

$$ n! = n * (n-1) * (n-2) * ... * 1 $$

(n은 2이상의 자연수, n이 1일 때는 그냥 1이다.)

 

이를 조금 다르게 쓰면 아래와 같습니다.

 

위의 팩토리얼 정의와 아래의 팩토리얼 정의는 완벽하게 같지만, 코드로 구현할 때 아이디어가 달라집니다.

 

위 수식의 정의대로 팩토리얼을 구현하면 반복문의 개념을 먼저 떠올리게 되지만, 아래 수식으로 팩토리얼을 구현하면 Recursion을 통한 구현에 대한 아이디어를 떠올릴 수 있습니다. 아래 수식에서 n <=1 일 때가 앞서 설명한 Base case이고, otherwise가 Induction step입니다.

 

우선 반복문으로 팩토리얼을 구현해봅시다.

// main.c
#include <stdio.h>
int main(int argc, char* argv[]) {
    int fact = 1;
    int n = 10;
    int i;
    for (i = 1; i <= n; i++) {
        fact *= i;
    }
    printf("result of factorial : %d\n", fact);
    return 0;
}

위와 같이 10!의 값을 구할 수 있습니다.

 

Recursion으로 팩토리얼 값을 구하려면 어떻게 할 수 있을까요?

우선 팩토리얼을 계산할 함수를 정의하고, Base case 코드를 먼저 작성한 뒤 Induction step을 작성하면 됩니다.

 

#include <stdio.h>
 
unsigned long long factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}
 
int main() {
    int n;
 
    if (n < 0) {
        printf("음수는 팩토리얼을 계산할 수 없습니다.\n");
    } else {
        unsigned long long result = factorial(n);
        printf("%d! = %llu\n", n, result);
    }
 
    return 0;
}

코드로 작성하면 위와 같습니다. base case인 n == 1일 때를 먼저 정의하고, Induction step인 n * (n-1)!을 정의 했습니다. 재귀 호출의 개념이 없다면 헷갈릴지만, 조금만 생각해보면 별로 어렵지 않습니다.

 

factorial()에 인수로 n(=10)이 주어지므로 else가 실행되어 n * factorial(n-1)이 return되는데, return되어 함수가 종료되기 전에  다시 factorial(n-1)이 호출 되어 같은 작업, 즉 n-1 * factorial(n-1-1)이 실행되는 것입니다. 위와 같은 작업이 n이 1이 될 때까지 반복됩니다. 결론적으로 n이 10이므로 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1의 결과 값이 return됩니다.

재귀호출은 base case가 없다면 무한으로 수행되므로 반드시 base case가 무엇인지 생각해보고 정의하는 것이 선행되어야 합니다

사실 팩토리얼 계산은 재귀호출로 계산하든, 반복문으로 계산하든 프로그램 실행 속도에 별 차이가 없습니다. 오히려 반복문으로 계산하는 것이 더 빠를 수도 있습니다.

 

그렇다면 거듭제곱(Power)도 재귀호출 방식으로 구현해봅시다. 우선 그 전에 반복문으로 먼저 구현해보면 아래와 같습니다.

// main.c
#include <stdio.h>
 
double power(double x, int n) {
    double p = 1;
 
    for (int i = 1; i <= n; i++) {
        p *= x;
    }
 
    return p;
}
 
int main() {
    double x = 2.0;
    int n = 10;
    double result = power(x, n);
 
    printf("%.1lf의 %d제곱 : %.2lf", x, n, result);
 
    return 0;
}

 

Recursion으로 구현하려면 어떻게 해야될까요? 우선 base case부터 생각해봅시다. base case는 n이 0일 때입니다.

거듭제곱을 순환으로 구현하려면 n이 짝수일 때와 홀수일 때를 나눠서 생각해야합니다. 사람의 계산할 때는 달라질게 없지만, 코드로 구현할 때는 조금 달라질 수 있습니다.

 

예를 들어서 설명하는게 더 쉬울 것 같습니다. 2^8을 계산한다고 하면, 이는 아래와 같이 쓸 수 있습니다.

$$ 2^8 = (2^2)^4 $$

 

즉 밑이 되는 2를 2제곱하고, 다시 그 2^2를 4제곱하면 2의 8제곱과 같습니다.  x^n에서 n이 짝수일 경우를 알아봤고, 홀수 일때는, 아래와 같이 쓸 수 있습니다.

$$ x^n = x * x^{n-1} $$

 

이러면 지수가 짝수가 되어 n이 짝수일 때와 같은 방법으로 재귀호출을 사용할 수 있습니다.

위와 같은 아이디어로 거듭제곱에 대한 recursion을 코드를 아래와 같이 구현할 수 있습니다.

 

// main.c
 
#include <stdio.h>
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);
}
 
 
int main() {
    double x = 2.0;
    int n = 8;
 
    printf("%.2lf의 %d제곱 : %.2lf", x,n, power(x, n));
}

 

n이 1이되었을 때 다시 호출하면 n이 0이 될 것이고(정수의 나눗셈은 소수점 이하가 버려지기 때문에) 그 때 base case가 실행되어 재귀호출이 종료됩니다.

 

어떻게 power()에서 x값이 반환될 수 있는지 헷갈릴 수 있는데, power(x, n)에서 n이 짝수이더라도 재귀호출을 하다보면 결국 n이 홀수가 되는 순간이 있기 때문에(예를 들면 n이 12일 때, 재귀호출이 두 번 수행되면 n은 3이 됨), 그 때 power()의 else가 수행되어 x^n이 return된다고 생각하면 될 겁니다.

 

거듭제곱 연산의 시간 복잡도는 반복으로 구현했을 때 O(n)이고, 순환으로 구현하면 O(log n)이라 순환이 훨씬 빠르다고 합니다. 사실 순환은 인간의 사고방식으로 프로그램의 실행 절차를 하나하나 따라가려고 하면 상당히 어렵습니다. 순환을 구현하기 위해서는 아이디어를 바탕으로 알고리즘을 도출하고, 이를 단순화하여 프로그램으로 구현하는 것이 좋습니다. 하나하나 전 과정을 이해하려고 하면 순환을 사용하기가 거의 불가능합니다

 

이 외에도 순환을 사용한 문제해결 방법으로 피보나치 수열, 하노이 탑 등이 있지만, 다른 블로그에도 포스팅이 많이 있을테니 궁금하신 분들은 직접 찾아보시면 좋을 것 같습니다.

 

[참고자료] 

1. 생능출판사, C언어로 쉽게 풀어쓴 자료구조