Did you know that you can navigate the posts by swiping left and right?

6. 재귀의 기본이해

21 Jan 2017 . category: Data_Structure . Comments
#korean #theory #data_structure

함수의 재귀적 호출의 이해

재귀함수의 이해

재귀함수란 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다.

논리적으로 불가능한 것 같지만, 재귀함수가 호출되면 재귀함수-복사본이 만들어져서 실행되기 때문에 가능하다. 그런데, 주의해야할 점이 있다. 재귀함수를 호출하면 반드시, 탈출할 구멍을 만들어라 는 것이다. 탈출조건(탈출할 구멍)이 없으면 재귀함수는 무한 루프를 만들어서 프로그램이 꺼지지 않는 마법에 걸릴 수 있다.

예제 - Factorial 코딩

간단한 예제로 확인해보자. 아래는 팩토리얼을 계산하는 C언어 코드이다.

int Factorial(int n) {
    if(n==0)
        return 1; // 탈출조건과 동시에 수학적으로 0! = 1 이다.
    else
        return n * Factorial(n-1); // 재귀함수 호출
}

예제 - 피보나치 수열 코딩

피보나치 수열은 다음과 같은 전개가 된다.

\[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … \]

쉽게 말하면 앞에거 2개 더한 것이 되고 이를 수학적으로 표현하면 다음과 같다.

\[ fib(n)= \begin{cases} 0 &n=1
1 &n=2
fib(n-1) + fib(n-2) &otherwise\end{cases} \]

이것을 코드로 옮기면 다음과 같다.

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

간단한 코드이다. 여기서 의문이 되는건 코드의 실행 순서이다.

Fibo(10)을 호출하면 Fibo(9) + Fibo(8)이 반환된다. 그런데, Fibo(9)도 모르고 Fibo(8)도 모른다. Fibo(9)를 알기 위해서 함수를 호출해보니 Fibo(8) + Fibo(7)이 반환됐다. ?? 어떤 순서로 실행될까?

결론을 말하면, 처음 호출된 함수의 결과가 나오면(재귀가 끝나면) 다음 함수로 넘어가는 식이다. 아래의 번호와 함께 살펴보자.

  1. Fibo(10)을 호출했더니 Fibo(9) + Fibo(8)이 반환됐다.
  2. Fibo(9)가 앞에 있는 함수이므로 재귀가 끝날 때까지 돌아야한다. Fibo(9)를 호출한다.
  3. Fibo(9)를 호출했더니 Fibo(8) + Fibo(7)이 반환됐다.
  4. Fibo(8)을 호출한다.
  5. … 무한 반복 … 무한 반복 …
  6. Fibo(2) = Fibo(1) + Fibo(0) = 1 이므로 재귀가 끝났다.
  7. Fibo(3)을 구하고, Fibo(4)를 구하고.. 반복해서 Fibo(9)를 드디어 구했다!
  8. Fibo(8)을 호출한다. (왜냐하면, Fibo(10) = Fibo(9) + Fibo(8)의 두번째 함수 호출)
  9. 위의 과정의 반복한다. 반복하고 반복해서 Fibo(8)을 구한다.
  10. Fibo(9)와 Fibo(8)을 구했으므로 Fibo(10)의 결과가 나왔다! 함수 끝!

이해가 안 될 수도 있다. 그러므로 아래의 이미지를 보고 순서를 이해하자.

Imgur-Fibonacci Algorithm

인터넷으로 대충 퍼온 사진인데.. 출처를 남기겠다. 나중에 비슷한 이미지로 내가 만들던가 해야지..

예제 - 하노이 타워(The Tower of Hanoi)

엄청 유명한 문제이다. 기둥이 A, B, C 이렇게 3개 있다고 할 때, A에서 C로 크기가 다른 원반으로 된 탑을 옮기는 문제이다. 조건은 크기가 큰 원반이 항상 아래에 있어야 한다는 것이다. 필자는 하노이 타워 문제를 혹성탈출 영화에서 처음 알게됐는데 뭐 지능을 테스트 한다나 뭐라나.. 딱히 중요한 것은 아니고 이런 문제가 있다는 사실만 알면 된다.

하노이 타워에 대한 이해는 다른 글이나 구글에서 찾아보는 것을 추천하고, 필자는 해결방법에 대해서만 적도록 하겠다. 알고리즘은 다음과 같다.

  1. 작은 원반 \(n-1\)개를 (맨 아래 원반을 제외한 원반) A에서 B로 이동한다.
  2. 맨 아래 원반(제일 큰 원반)을 A에서 C로 이동한다.
  3. 1번에서 옮긴 원반 \(n-1\)개를 B에서 C로 이동한다.

이를 C언어 코드로 표현해보면

// A에 있는 num개의 원반을 B를 거쳐 C로 이동
void HanoiTowerMove(int num, char A, char B, char C) {
    if(num == 1) // 탈출조건: 이동할 원반이 1개일 때.
        printf("원반 1을 %c에서 %c로 이동한다. \n", A, C);
    else {
        HanoiTowerMove(num-1, A, C, B); // 1단계: A에서 B로 이동한다.
        printf("원반 %d을(를) %c에서 %c로 이동한다. \n", num, A, C); // 2단계: A에서 C로 이동한다.
        HanoiTowerMove(num-1, B, A, C); // 3단계: B에서 C로 이동한다.
    }
}

요러면 구현이 된다. 은근히 혼자서 생각하려고 하면 좀 짜증나는내가 뉴비라서 그런걸까나 그런 문제이다. 사실 하노이 타워, 나한테 하라고 실물로 갖다주면 아마 못하고 때려치울게 분명한데, 이런 관점에 있어서는 컴퓨터는 참 똑똑하다는 그런 생각이 든다. 알고리즘 만든 사람이 더 똑똑한거겠지.

Me

Coding Future, Decoding Society.