[자료구조론] 2주차: 순환

순환(Recursion)

정의 자체가 순환적인 경우 적합하다.

주어진 문제를 더 작은 동일한 문제로 분할해 해결(분할 정복: Divide and Conquer)

 

Ex) Factorial

$n!$은 $n \geq 1$에 대해서는 $n(n-1)!$, $n = 0$에 대해서는 1로 정의할 수 있다.

int factorial(int n)
{
    return (n <= 1) ? 1 : (n * factorial(n - 1));
}

$n!$

$= n \times (n - 1)!$

$= n \times (n - 1) \times (n - 2)!$

$\cdots$

$= n \times (n - 1) \times (n - 2)! \times \cdots \times 2!$

$= n \times (n - 1) \times (n - 2)! \times \cdots \times 2 \times 1!$

$= n \times (n - 1) \times (n - 2)! \times \cdots \times 2 \times 1$

 

Divide and conquer

$n \times (n - 1)!$에서 $n$은 이미 해결된 부분, $(n - 1)!$은 남아 있는 부분(더 작은 동일한 문제)

 

* 순환 알고리즘에는 반드시 순환을 멈추는 부분이 필요하다. 안 그러면 무한 호출돼서 메모리 터짐

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

 

 

팩토리얼을 반복으로 구현하면 다음과 같다.

int factorial_iter(int n)
{
    int result = 1, i;
 
    for (i = 1; i <= n; result *= i++);
 
    return result;
}

 

Recursion VS Iteration

시간 복잡도: 둘 다 $O(n)$

공간 복잡도: 순환은 함수 호출 오버헤드, 반복은 오버헤드가 적다.

-> 왜 순환인가?: 간결한 코드, 반복으로 표현하기 어려운 순환도 있음

 

 

Ex2) Power by recursion

$\begin{cases}(x^2)^{\frac{n}{2}} & n\;is\;even\\x(x^2)^{\frac{n-1}{2}} & n\;is\;odd\end{cases}$

 

- $2^{10}$

$2^{10} = (2^2)^{\frac{10}{2}}=(2^2)^5$

$4^5 = 4 \times 4^4 = 4 \times ((4^2)^{\frac{4}{2}}) = 4 \times 16^2$

$16^2 = (16^2)^1$

$256^1 = 256^1 \times (256^2)^0 = 256 \times 65536^0$

$65536^0 = 1$

 

반복의 경우 $x^n$을 구하려면 대략 $n$번의 계산 필요 -> $O(n)$

순환의 경우 대략 $x^n$에 대해 $n=2^k$라 하면 $k$번의 계산 필요

즉 $\log_{2}{n}$번의 연산을 요하므로  $O(\log{n})$

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

$cf.$ $x\;*\;x$ 대신 $power(x, 2)$를 쓰면 $power(2, 2)$가 무한히 호출됨