[자료구조] Recursion

1. Recursion

  Recursion 이란?

    => algorithm이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법

    => 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법

 

  Recursion을 사용한 algorithm

    => factorial 값 구하기

    => Fibonacci 수열

    => 이항계수

    => Hanoi 탑

    => 이진탐색

 

  factorial 값 구하기

    => factorial 이란? n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다.

예시

  factorial 구현 방법

    => 1번째 방법

    => factorial1 함수와 그 외의 sub 함수를 따로 제작

int factorial1(int n) {
    if( n<= 1 ) return(1);
    else return (n * factorial2(n-1));
}
int factorial2(int n) {
    if( n<= 1 ) return(1);
    else return (n * factorial3(n-1));
}
int factorial3(int n) {
    if( n<= 1 ) return(1);
    else return (n * factorial4(n-1));
}
//...

    => 2번째 방법

    => Recursion을 이용하여 자기 자신을 다시 호출

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

 

  factorial 함수의 순환 호출 순서

 

  순환 Algorithm의 구조

    => 순환 algorithm은 순환 호출을 하는 부분 / 순환 호출을 멈추는 부분이 필요하다.

    => 순환 호출을 멈추는 부분이 없다면 오류가 발생할 때까지 무한정 호출하게 된다. (무한루프)

 

---

2. 순환과 반복

  Computer에서의 되풀이

    => 순환(recursion) : 순환 호출 이용

    => 반복(iteration)  : for또는 while을 이용한 반복

 

  순환

    => 순환적인 문제에서는 자연스러운 방법

    => 함수 호출의 overhead

 

  반복

    => 수행속도가 빠르다.

    => 순환적인 문제에 대해서는 program 작성이 아주 어려울 수도 있다.

 

  대부분의 순환은 반복으로 바꾸어 작성할 수 있다.

// Factorial의 반복적 구현
int factorial_iter(int n) {
    int k, v = 1;
    
    for(k = 1; k <= n; k++)
        v = v * k;
    
    return v;
}

 

  ex) 거듭제곱 문제

    => 순환적인 방법이 반복적인 방법보다 더 효율적인 예

    => 숫자 x의 n제곱 값을 구하는 문제 : Xⁿ

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

// 순환적인 방법
double sqr_recur(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의 10제곱이라면 2^10 -> 2^9 -> 2^8 ... 2²  -> 2¹ -> 2º

    => 시간복잡도 : O(log₂ n)

 

    => 반복적인 방법과 순환적인 방법의 비교

	반복적인 방법	순환적인 방법
시간 복잡도	O(n)	O(log₂ n)

 

 

  ex) Fibonacci 수열

    => 순환 호출을 사용하면 비효율적인 예

    => 순환 호출을 사용할 경우 이전에 계산한 값을 다시 계산하게 됨

// 반복적인 방법
int fib_iter(int n) {
    if(n < 2) return n;
    else {
        int i, cur, fi1 = 1, fi2 = 0;
        
        for(i = 2; i <= n; i++) {
            cur = fi1 + fi2;
            fi2 = fi1;
            fi1 = cur;
        }
        return cur;
    }
}

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

 

 

 

 

 

 

 

https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9