재귀함수란? _ C언어의 재귀호출을 이용해서 구현한 하노이탑을 예로서.

재귀적이다??

한 알고리즘이 문제를 보다 작은 입력을 갖는 동일한 문제로 단순화시켜 해결한다면 이 알고리즘은 재귀적임.

하노이탑

#include <stdio.h>
#include <string.h>

void hanoi(char from, char temp, char to, int n);

int count = 0;

void main(void)
{
   int num;

   printf("Enter the number of Hanoi disk : ");
   scanf("%d", &num);

   hanoi('A', 'B', 'C', num);
}

void hanoi(char from, char temp, char to, int n)
{
   if (n==1) {
      count++;
      printf("%d : disk %d, %c -> %c\n", count, 1, from, to);
   }
   else {
      hanoi(from, to, temp, n-1);
      count++;
      printf("%d : disk %d, %c -> %c\n", count, n, from, to);
      hanoi(temp, from, to, n-1);

   }
}

재귀함수는 A함수안에서 A(혹은 B와 같은 타 함수)함수가 다시 불려지는 것입니다.
(만약 B와같은 타 함수가 불려졌을 경우에는 B함수내에서는 A함수를 부르거나 하는 식의 무한적 호출이 있어야합니다.)
위의 C언어 소스같은 경우에는 hanoi함수가 자신을 다시 또 호출하는 것을 볼 수 있습니다.

재귀함수는 이런식의 무한적으로 자신이나 타 함수와 연계되어 계속적으로 반복적인 연산이 이루어지는데
(위의 C언어 소스에서는 재귀호출시에 count개념의 n변수를 1씩 차감하고 있는 것을 볼 수 있습니다.)
이러한 반복적인 연산을 통해서 특정 터미널조건을 부여해야합니다.
(무한 loop를 위해 재귀함수를 쓰는 것은 아니니까요.)

즉 문제가 주어졌을 때 해결방법을 우선적으로 고민해야합니다.
해결방법이 이하 조건을 만족한다면
   1. 주어진 문제가 보다 작은 입력을 가지는 특정 규칙이 있는가?
   2. 어떤 터미널 조건이 있는가?
이는 재귀함수를 이용함이 효율적입니다.
(다만 메모리와 실행속도때문에 재귀함수를 사용하는 것은 특정 경우를 제외하고는 지양되고 있습니다.
 그 이유는 훗날 개발자로서 지내다보면 알게될시 포스트하도록 하겠습니다 -_-;;)

위의 하노이탑의 경우 제안된 문제의 요지는 이러합니다
하노이탑은 N층의 원판이 쌓여있는 탑이며
하위의 원판은 상위 원판보다 절대 같아서도, 작아서도 안된다.
한번에 한개의 판만을 옮길 수 있다.
N층의 원판이 A, B, C 세개의 탑 중 A에 모두 있다고 가정을 합니다.
그럼 B, C중 한 곳에 이 N층의 원판을 옮겨야하는데 이때 편의상 중간에 B탑이 있고 C탑에 옮긴다고 가정합니다.

재귀함수를 이용하게 될 경우 생각할 수 있는 방법은 바로 N-1번째 층을 남겨두고 모두 옮기는 겁니다.
다시말해서 가장 하위층만 남기고 모두 층을 옮기는 겁니다.
위의 hanoi함수를 계속 따라가게되면 첫번째 hanoi재귀함수에서 temp(빈 탑)로 계속 이동하게 됩니다.
그리고 두번째 hanoi 재귀함수에서는 옮기고 남은 층을 본래 옮기려는 탑으로 옮깁니다.
이렇게 되면 첫번째 재귀함수를 통해 N-1번째 층까지의 모든 층들은 temp로 모두 이동하게 되고
마지막 남은 층이 본래 옮기려는 탑(C, to)으로 옮겨지게 됩니다.
이후에는 B탑이 from이 되고 A탑이 temp(B)이 되게 되는 겁이며 C는 본래 옮기려는 탑으로 남게 됩니다.

쉽게 이해를 도우려고 했는데 잘됐는지 모르겠네요.
재귀함수는 알고 사용하면 엄청나게 편합니다.
재귀함수를 쓸 때에는 늘 터미널 조건과 문제보다 작아지는 일정 반복규칙을 찾아야합니다^^

하노이탑을 반복문으로 구현하는 경우도 있는데 아직 시도하진 않았지만 만약 반복문을 이용하여 구현한 경우에는
그 소스는 현금거래가 이루어질만큼 어렵다고 하네요.