[Data Structure] 재귀(recursion)와 반복(iteration)

---

재귀 (Recursion)

 

재귀함수는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 가장 대표적 예가 팩토리얼, 피보나치 수열이다. 팩토리얼은 아래와 같이 정의된다.

$$ n ! = \begin{cases} 1 & \quad n = 0 \\ n \times (n-1) ! & \quad n \geq 1 \end{cases} $$

 $ n ! $ 을 계산하기 위해 $ (n-1) ! $ 을 계산하는 것이다. 결국 팩토리얼 계산을 위해 다시 팩토리얼을 계산해야 한다.

피보나치 수열 역시 아래와 같이 정의되기 때문에 재귀함수라 할 수 있다.

$$ F_0 = 0, \quad F_1 = 1, \quad F_{n+2} = F_{n+1} + F_{n} $$

$ F_{n+2} $ 를 계산하기 위해 $ F_{n+1} $ 과 $ F_{n} $ 을 계산해야 하고, 이는 피보나치 수열의 값을 계산하기 위해 피보나치 수열의 값을 계산해야 하기 때문에 재귀함수이다.

그런데 생각해보면 자기 자신을 계산하기 위해 자기 자신을 계산해야 한다면, 즉 자기 자신을 계산하기 위해 다시 자기 자신을 호출해야 한다면, 영원히 끝나지 않는 반복이 일어나지 않을까 하는 생각이 들 수 있다. 따라서 재귀함수에서는 종료조건(base condition)이 중요하다. 즉 어떤 호출에서는 자기 자신을 다시 호출하는 것이 아니라 특정 값을 반환해야 한다. 위 팩토리얼은 1 혹은 0 일때 1 을 반환하고, 피보나치 수열은 0 일때 0 을, 1 일때 1 을 반환한다.

만약 종료조건이 없는 재귀함수를 호출하게 되면 아래 이미지처럼 무한 루프를 돌게된다.

 

출처: https://hyeonsi.tistory.com/75

 

---

수학적 귀납법

 

절차적 방법론을 생각해본다면, 어떤 함수가 참인지 확인하기 위해서는 차례차례 대입하며 확인해야 한다. 예를 들어 어떤 함수 $ P $ 가 있다고 가정해보자. 절차적으로 확인하려면 $ P(0) $ 이 참인지 확인하고, $ P(1) $ 이 참인지 확인하고, $ P(2) $ 가 참인지 확인하고, ... 계속 확인해야 한다.

수학적 귀납법을 적용하여 생각해본다면 $ P(0) $ 이 참인지 확인하고, $ P(n) $ 이 참이라 가정했을 때 $ P(n+1) $ 이 참이라면 모든 $ n $ 에 대해 $ P(n) $ 이 참이다. 추론규칙으로 나타낸다면 아래와 같다.

$$ \begin{align*} & P(0) \\ & \forall n \geq 0 (P(n) \rightarrow P(n+1)) \\ \hline & \therefore \forall n \geq P(n) \end{align*} $$

도미노를 예시로 설명해본다면, 첫 번째 도미노가 넘어지는 것을 확인하였다. 만약 $ k $ 번째 도미노가 넘어진다고 가정할 때 $ k + 1 $ 번째 도미노가 넘어지는 것을 확인하였다. 그렇다면 당연히 첫 번째 도미노부터 $ k $ 번째 도미노까지는 모두 넘어졌을 것이다. 즉 $ P(0) $ 이 참이고, $ P(k) $ 이 참이라 가정했을 때 $ P(k+1) $ 이 참이면 $ P(1) $ 부터 $ P(k) $ 는 모두 참인 것이다.

예를 들어 처음 $ n $ 개 홀수의 합은 $ n^2 $ 과 동일하다는 명제를 생각해보자. 이는 아래와 같이 나타낼 수 있을 것이다.

$$ \forall n \geq 1 : \sum^n_{i=1}{2i-1} = n^2 $$

이를 증명해보자. 먼저 1 에 대해서 어떠한지 확인하자. $ 2 \times 1 - 1 = 1 = 1^2 $ 이므로 참이다. 이제 $ n $ 에 대해서 참이라 가정하고, 즉 $\sum^n_{i=1}{2i-1} = n^2 $ 이라 가정하고 $ n + 1 $ 을 확인해보자.

$$ \sum^{n+1}_{i=1}{2i-1} = \left( \sum^{n}_{i=1}{2i-1} \right) + (2(n+1)-1) = n^2 + 2n + 1 = (n+1)^2 $$

따라서 $ n + 1 $ 일 때 참이고, $ P(n) $ 은 참이라 할 수 있다.

이러한 방법론을 통해 재귀함수를 분석하고, 평가해볼 수 있겠다.

 

---

재귀와 반복

 

재귀함수를 다시 생각해보자. 재귀함수는 종료 조건을 만날 때까지 자기 자신을 반복적으로 호출하는 함수이다. 예를 들어, C 언어로 재귀함수를 작성하고 이를 호출하면, 해당 함수는 종료 조건을 만날 때까지 계속해서 자기 자신을 호출하게 된다. 이때 컴퓨터 내부에서는 어떤 일이 일어날까 생각해보자. 재귀함수가 호출하는 함수는 실제로는 같은 함수이지만, 동일한 메모리 공간을 사용하는 것이 아니라 새로운 메모리 공간을 할당받아 동작하게 된다. 즉, 매번 새로운 메모리 공간에 동일한 연산을 수행하는 함수가 호출되는 것이다. 따라서 종료 조건을 만나기 전까지 자기 자신을 한 번 호출하는 재귀함수가 세 번 호출된다면, 메모리 공간을 새롭게 세 번 차지하게 된다. 즉, 재귀 호출이 반복될수록 스택 메모리 소모가 증가하게 된다.

함수를 호출하면서 소모되는 것은 메모리만이 아니다. 함수 호출 자체에도 다양한 연산이 발생하기 때문에, 호출될 때마다 시간이 소모된다. 따라서 재귀함수는 일반적으로 가독성이 좋을지 모르지만, 시간 복잡도와 공간 복잡도 측면에서 단점을 가지고 있다. 이러한 이유로 재귀함수를 반복문으로 바꿔 사용하는 것이 시간 복잡도와 공간 복잡도 측면에서 더 효율적일 때가 많다. 그러나 어떤 측면에서는 재귀함수로만 구현할 수 있는 함수도 존재하며, 재귀함수로 구현하는 것이 시간 복잡도 측면에서 더 우수할 때도 있으니 유의해야 한다.

 

---

재귀-반복 전환 | C

 

• 팩토리얼

팩토리얼의 정의는 다음과 같았다.

$$ n ! = \begin{cases} 1 & \quad n = 0 \\ n \times (n-1) ! & \quad n \geq 1 \end{cases} $$

이를 재귀함수로 구현한다면 아래와 같이 구현할 수 있다.

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

위 펙토리얼 함수를 반복문으로 바꿔보면 아래와 같이 구현할 수 있다.

int Factorial(int n) {
    int temp = 1;
    for (int i = 0; i <= n; i++) {
        temp *= i;
    }
    return temp;
}

팩토리얼의 경우에는 결과적으로 같은 연산을 하기 때문에 반복문을 사용하는 것이 재귀함수를 사용하는 것보다 더 효율적이다.

 

• 거듭제곱

거듭제곱을 일반적인 정의대로 구현한다면 아래와 같이 반복문을 사용할 것이다.

int power(int x, int n) {
    int temp = 1;
    for (int i = 0; i < n; i++) {
        temp *= x;
    }
    return temp;
}

그러나 재귀를 이용하여 다음과 같이 효율적으로 계산할 수도 있다.

int power(int 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);
    }
}

이는 $ (x)^{10} = (x^2)^5 $ 을 생각해보면 쉽게 이해할 수 있다. 괄호 밖 거듭제곱이 연산 횟수라 생각하면 된다.

반복문을 이용한 거듭제곱 함수는 시간복잡도가 $ O(n) $ 이었지만, 재귀함수로 구현한 거듭제곱 함수는 계산마다 절반으로 줄어들기 때문에 시간복잡도가 $ O(\log_n) $ 이다. 따라서 이 경우 공간복잡도 측면에서 손해가 있을지 몰라도 시간복잡도 측면에서 재귀함수로 구현하는 것이 유리하다. 백준의 곱셈(링크)을 활용하여 연습할 수 있다.

 

• 피보나치 수열

피보나치 수열의 정의는 다음과 같았다.

$$ F_0 = 0, \quad F_1 = 1, \quad F_{n+2} = F_{n+1} + F_{n} $$

이를 재귀함수로 구현한다면 아래와 같이 구현할 수 있다.

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

그런데 이 피보나치 수열을 계산하는 재귀함수는 자기 자신을 호출하는 경우 한 번도 아니고 두 번이나 호출한다. 따라서 단순히 메모리 공간, 시간 문제 뿐 아니라 계산된 피보나치 수열을 다시 계산하게 된다. 예를 들어 함수에 $ n $ 으로 4 를 넣었다고 생각해보자. 4 는 0 도 1 도 아니기 때문에 Fibonacci(3) 과 Fibonacci(2) 를 호출할 것이다. 그럼 다시 Fibonacci(3) 은 Fibonacci(2) 와 Fibonacci(1) 을 Fibonacci(2) 는 Fibonacci(1) 과 Fibonacci(0) 을 호출할 것이다. 그리고 또 다시 Fibonacci(2) 는 Fibonacci(1) 과 Fibonacci(0) 을 호출할 것이다. 

결국 위 그림처럼 호출되는데, Fibonacci(0) 은 2번 호출되었고, Fibonacci(1) 은 3번 호출되었으며, Fibonacci(2) 도 2번 호출되었다. 한 번 씩만 계산하면 되는데 여러번 호출되면서 시간, 메모리 측면에서 손해를 본 것이다.

따라서 이 경우 아래와 같이 피보나치 수열을 차근차근 계산해나가면서 그 전, 전전 피보나치 수열을 더해가는 식으로 반복문을 통해 피보나치 수열을 계산하는 함수를 구현할 수 있다.

int Fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }
    int pastpast = 0, past = 1, now;
    for (int i = 2; i <= n; i++) {
        now = pastpast + past;
        pastpast = past;
        past = now;
    }
    return now;
}

혹은 배열에 피보나치 수열 자체를 저장해서 사용할 수도 있을 것이다. 이를 메모리제이션(memorization)이라 한다. 아래와 같이 구현할 수 있다.

int fib[n+1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
    fib[i] = fib[i-1] + fib[i-2];
}

백준의 피보나치 수(링크)를 통해 연습할 수 있다.

 

• 하노이 탑

하노이 탑 문제는 세 개의 말뚝에 $ n $ 개의 디스크가 크기가 작은 디스크가 위로 오도록 꽂혀있는 상태에서 크기가 작은 디스크가 항상 위에 있도록 유지하면서 다른 말뚝으로 디스크를 모두 옮기는 문제이다. 이때 이동을 최소로 하는 것이 중요한데, 예를 들어 3 개의 디스크를 가진 하노이 탑이 있다고 가정하면 아래와 같이 이동시켜야 할 것이다.

출처: edurev.in

이를 단순화시켜서 위 두 개의 디스크를 하나로 생각해보자. 그렇다면 아래와 같이 이동시켜야 할 것이다.

출처: edurev.in

그런데 생각해보면 가장 위 두 개의 디스크를 이동시키는 방법 역시 동일하다. 즉 세 개의 디스크를 이동시키는 것을 간단히 하면 위 두 개의 디스크를 한 곳으로 이동시키고, 가장 아래 디스크를 최종 위치에 이동시킨 다음에 마지막으로 두 개의 디스크를 최종 위치로 이동시키면 된다. 네 개의 디스크를 가정해도, 역시 위 세 개의 디스크를 한 곳으로 이동시키고, 가장 아래 디스크를 최종 위치에 이동시킨 다음에 마지막으로 세 개의 디스크를 최종 위치로 이동시키면 된다. 즉 하노이 탑을 최소한으로 움직이면서 이동시키는 횟수는 디스크가 하나 적은 하노이 탑을 두 번 움직이고, 가장 큰 디스크를 한 번 움직이는 횟수를 더한 것과 같다. 따라서 하노이 탑의 이동 횟수를 구하는 함수를 $ H(n) $ 이라 한다면 다음이 성립한다.

$$ H(1) = 1, \quad H(n) = 2 \times H(n-1) + 1 $$

역시 재귀함수와 반복문으로 구현할 수 있고, 다음은 재귀함수로 구현한 하노이 탑 이동 횟수를 구하는 함수이다.

int Hanoi(n) {
    if (n == 1) {
        return 1;
    } else {
        return 2 * Hanoi(n-1) + 1;
    }
}

다음은 반복문으로 구현한 하노이 탑 이동 횟수를 구하는 함수이다.

int Hanoi(n) {
    if (n == 1) {
        return 1;
    }
    int past, now;
    past = 1;
    for (int i = 2; i <= n; i++) {
        now = 2 * past + 1;
        past = now;
    }
    return now;
}

백준의 하노이 탑(링크)과 하노이 탑 이동 순서(링크)를 통해 응용을 연습할 수 있다.