[C/C++] 순환, 재귀 호출

순환(Recursion)

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법

순환을 이용하는 가장 쉬운 예시인 팩토리얼을 생각해보자

3! 을 계산하기 위해선 어떻게 해야 할까?

3! = 3 * 2 * 1 이다

위 식을 다르게 표현해보자

3 * 2! 로 표현할 수도 있다

2! 는 어떻게 계산할까?

2 * 1 이다 또한 2 * 1! 로 표현할 수도 있다

즉 n! 를 계산하기 위해서는

(n - 1)! 를 계산해야하고 이를 계산하기 위해서는 (n - 2)! 를 계산해야 한다

여기서 공통점이 있다

전부 팩토리얼이라는 것이다

즉 팩토리얼을 계산하는 함수를 반복하면 계산할 수 있다

이렇게 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법을 분할 정복(divide and conquer)이라고 부른다

위 아이디어를 코드를 보면서 다시 떠올려보자

int factorial(int n)
{
    if (n <= 1)                            //1! 은 1 이므로 1 반환
        return 1;
    else
        return (n * factorial(n - 1));    //함수를 다시 불러와 n * (n-1)! 계산
}

factorial(3) 은 어떻게 동작할까? 한 번 생각해보자

1. 3은 1보다 크므로 3 * 2! 로 factorial(2) 를 호출한다

2. 같은 이유로 factorial(2) 는 factorial(1) 을 호출한다

3. 1은 1보다 작거나 같으므로 factorial(1) 은 1 을 반환한다

4. factorial(2) 는 2 * 1 의 결과인 2 를 반환한다

5. factorial(3) 은 3 * 2 의 결과인 6을 반환한다

6. 이로서 3! 의 결과값을 얻어낸다

그렇다면 시스템적으로 어떻게 동작할까?

이를 이해하기 위해선 스택의 개념이 필요하다

스택은 쉽게 말해서 책을 쌓아올려서 꺼낼 때는 위에서부터 차례대로 꺼내는 방식의 저장소다

순환이 끝날 때 다음 코드를 실행하기 위한 복귀주소가 시스템 스택에 저장된다

이러한 공간을 활성 레코드(activation record)라고 한다

factorial(3) 이 시스템 스택에 저장되고 factorial(2) 가 호출된다

그 후 factorial(2) 가 시스템 스택에 쌓이고 factorial(1) 이 호출된다

factorial(1) 이 시스템 스택에 쌓이고 1을 반환한 후 이전 스택인 factorial(2) 로 돌아간다

반복하여 factorial(3) 이 값을 반환한다

잘 이해가 안된다면 다음 코드를 그림으로 표현해보자

void recurs(argumentlist)
{
    statements1
    if (test)
        recurs(arguments)
    statement2
}

계단을 올라갈 때와 내려갈 때는 서로 순서가 반대다

계단을 올라간다고 생각해보자

올라갈 때는 순서대로 올라가지만 내려올 때는 반대로 내려온다

즉 statements1을 순서대로 처리하면서 처리할 때마다 그 자리에 statements2를 남겨둔다

그리고 순환이 끝나고 남은 statements2를 반대 순서로 처리한다

---

어떤 코드 구조를 순환 알고리즘이라고 부를까?

자기 자신을 호출한다고 무조건 순환인 것은 아니다

순환하는 부분이 있으면 반드시 그 순환을 매듭지어주는 부분이 있어야 한다

위 팩토리얼 계산 함수에서는

if 문을 통해 1을 반환하면서 순환을 끝맺어주었다

되풀이하는 방식에는 반복하는 방법도 있다

for 문과 while 문이 이에 해당하는 방법이다

순환 중에서 순환 호출이 끝에서 이루어지는 순환을 꼬리 순환(tail recursion)이라고 부르는데

이러한 경우 반복 알고리즘으로 쉽게 바꾸어 쓸 수 있다

반복을 쓰면 편한데 왜 이해하기 어려운 순환을 공부해야 하는가?

하지만 해결하고자 하는 문제에 따라서 반복이 효율적일 수도 있고 비효율적일 수도 있다

거듭제곱을 계산하는 경우

반복적인 방법은 같은 수를 n번 반복해야 한다

하지만 순환적인 방법을 사용할 경우

위 식을 이용하여 코드를 작성하면 적은 횟수로 결과값을 계산할 수 있다

위 코드는 다음 포스팅에 보여주도록 하겠다 독자들도 직접 풀어보는 기회를 가졌으면 좋겠다

그 반대의 경우

피보나치 수열을 구하는 코드를 보면서 비교해보자

피보나치의 점화식

int fib(int n)
{
  if ( n == 0 )
    return 0;                              //a_0 = 0
  else if ( n == 1 )
    return 1;                              //a_1 = 1
  else
    return ( fib(n - 1) + fib(n - 2) );    //a_n = a_n-1 + a_n-2
}

fib(4) 가 어떻게 계산되는지 생각해보자

1. fib(4) 는 fib(3) 과 fib(2) 을 호출한다

2. fib(2) 는 fib(1) 과 fib(0) 을 호출한다

3. fib(0) 은 0을 반환한다

4. fib(1) 은 1 을 반환한다

5. fib(2) 는 0 + 1 = 1 을 반환한다

6. fib(3) 은 fib(2) 와 fib(1) 을 호출한다

7. fib(1) 은 1 을 반환한다

8. fib(2) 는 fib(1) 과 fib(0) 을 호출한다

9. fib(0) 은 0 을 반환한다

10. fib(1) 은 1 을 반환한다

11. fib(2) 는 0 + 1 = 1 을 반환한다

12. fib(3) 은 1 + 1 = 2 를 반환한다

13. fib(4) 는 2 + 1 = 3 을 반환한다

뭔가 이상하지 않은가?

색이 같은 부분을 확인해보자

이미 반환했던 부분을 다시 한 번 반복하는 바보 같은 계산을 하고 있다

이런 경우가 있기에 무조건 순환이 빠르다고 할 수는 없다

그렇다면 반복적인 방법은 어떨까?

---

마지막으로 순환으로 해결할 수 있는 문제 하나를 소개하고 끝마치도록 하겠다

그 유명한 하노이탑 문제다

하노이탑의 규칙

1. 한 번에 하나의 원판만 이동할 수 있다

2. 맨 위에 있는 원판만 이동할 수 있다

3. 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다

4. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다

위 규칙들을 참고해서 n개의 원판의 하노이탑 문제를 해결하는 코드를 작성해보기로 하자

1. n - 1 개의 원판을 중간의 막대에 옮긴다
   

2. 남은 하나의 원판을 오른쪽 막대에 옮긴다

3. n - 1 개의 원판을 오른쪽 막대에 옮긴다

#include <stdio.h>
 
void hanoi(int n, char from, char tmp, char to)
{
    if ( n == 1 )
    {
        printf("원판 1 을(를) %c에서 %c 로(으로) 옮긴다.\n", from, to);
    }
    else
    {
        hanoi(n - 1, from, to, tmp);                                         //1번
        printf("원판 %d 을(를) %c에서 %c 로(으로) 옮긴다.\n", n, from, to);    //2번
        hanoi(n - 1, tmp, from, to);                                         //3번
    }
}
 
main()
{
    hanoi(3, 'A', 'B', 'C');
}