순환 알고리즘과 반복 알고리즘

 순환 알고리즘

순환 호출의 비효율성

순환 알고리즘이란 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법을 말한다. 문제의 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법이다. 그러나, 예로 들어 피보나치값을 계산할 때 같은 항을 중복해서 계산했던 것처럼 함수 호출의 오버헤드 문제가 발생할 수 있다.

순환 알고리즘은 순환 호출을 하는 부분과 순환 호출을 멈추는 부분으로 이루어져 있다.

 

 반복 알고리즘

반복 알고리즘은 for나 while을 이용하여 반복한다. 수행속도가 빠르지만, 순환적인 문제에 대해서는 프로그램 작성이 어려울 수 있다.

 

 

 다양한 알고리즘

1. 팩토리얼 구하기

int factorial_recur(int n) {  // 순환적 방법
    if (n == 1) return 1;
    return n * factorial(n-1);
}

int factorial_iter(int n) {  // 반복적 방법
    int result = 1;
    for(int i = n; i >= 1; i--)
       result *= i;
    return result;
}

 

2. 거듭제곱값 (순환 > 반복)

double power_recur(double x, int n) {  // 순환적 방법
    if (n == 0) return 1;
    else if(n % 2 == 0) return power_recur(x*x, n/2);
    else return x * power_recur(x*x, (n-1)/2);
}

double power_iter(double x, int n) {  // 반복적 방법
    double result = 1.0;
    for(int i = 0; i < n; i++)
        result *= x;
    return result;
}

 

3. 피보나치 수열(반복 > 순환)

int fib_recur(int n) {  // 순환적 방법
    if (n <= 1) return n;
    return fib_recur(n-2) + fib_recur(n-1);
}

int fib_iter(int n) {  // 반복적 방법
    if (n <= 1)
        return n;
    
    int pp = 0, p = 1;
    int result = 0;
    for(int i = 2; i <= n; i++) {
        result = pp + p;
        pp = p;
        p = result;
    }
    return result;
}

 

3. 이항계수

int nCk_recur(int n, int k) {  // 순환적 방법
    if (k == 0 || n == k) return 1;
    return nCk_recur(n-1, k-1) + nCk_recur(n-1, k);
}

int nCk_iter(int n, int k) {  // 반복적 방법
    return fac(n) / (fac(k) * fac(n-k));
}

 

4. 하노이의 탑(반복 > 순환)

void hanoi_tower_recur(int n, char from, char tmp, char to) {  // 순환적 방법
    if (n == 1) printf("원판 1을 %c에서 %c으로 옮긴다.\n", from, to);
    else {
        hanoi_tower_recur(n-1, from, to, tmp);
        printf("원판 %d을 %c에서 %c으로 옮긴다.\n", n, from, to);
        hanoi_tower_recur(n-1, tmp, from, to);
    }
}

int main() {
    hanoi_tower_recur(4, 'A', 'B', 'C');
    return 0; 
}

 

5. 이진탐색

int binarySearch_recur(int arr[], int left, int right, int target) {  // 순환적 방법
    if (left > right) 
        return -1;
    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] > target) return binarySearch_recur(arr, left, mid-1, target);
    else binarySeach_recur(arr, mid+1, right, target);
}

int binarySearch_iter(int arr[], int left, int right, int target) {  // 반복적 방법
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) right = mid-1;
        else left = mid + 1;
    }
    return -1;
}

 

 

 

출처) C언어로 쉽게 풀어쓴 자료구조