재귀

recursive

 

재귀함수

 

나무위키에 따르면 재귀함수 (recursion) 는 정의 단계에서 자신을 재참조하는 함수를 뜻한다.

어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. 일단 무언가를 설명할 때 자기를 포함한 것이라고 이해하면 편하다.

 

즉, 재귀함수는 함수 내에서 자기 자신을 다시 호출하여 복사본을 만든 후 복사본을 실행하는 함수이다.  

 

void recursive(void)
{
printf("recursive call");
recursive();
}​

 

 

재귀함수를 사용할 때 탈출조건을 정립하지 않으면 계속해서 재귀함수가 실행된다. 

따라서 함수가 실행을 멈추게 되는 탈출 조건의 정립이 필요하다. 

 

재귀함수의 활용으로 팩토리얼 계산, 피보나치 수열, 하노이 탑이 있다. 

 

 

피보나치 수열 

 

피보나치 수열은 앞에 있는 두 개의 항을 더해 항을 추가하는 것이다. 

 

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

 

위의 형태로 전개된다. 

 

 

#include <stdio.h>

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

int main(void)
{
    int i;
    for(i=1; i<10; i++)
        printf("%d ", Fibo(i));
    return 0;
}​

 

하노이 탑 

 

하노이 타워는 재귀함수로 접근해야 그나마 쉽게 풀리는 문제이다.

 

하나의 막대에 크기 순대로 쌓여있는 원반들을 크기 조건을 만족하며 다른 막대에 그대로 옮기는 방법이다. 

 

우선 3개의 원반을 옮겨야 한다고 생각해 보자. 

---

막대 1에 있는 원반들을 막대 3으로 옮겨야 한다. 

이때, 원반은 한 번에 하나씩 옮길 수 있으며, 작은 원반은 큰 원반 아래에 존재할 수 없다는 조건이 있다. 

 

1. 막대 1에서 제일 위에 올려져 있는 원반을 막대 3으로 이동한다. 

2. 그다음 원반을 막대 2로 이동한다. 

3. 막대 3에 있는 원반을 막대 2로 이동한다. 

4. 막대 1에 남은 가장 큰 원반을 막대 3으로 이동한다. 

5. 막대 2에 있는 가장 작은 원반을 막대 1로 이동한다. 

6. 막대 2에 있는 원반을 막대 3으로 이동한다. 

7. 막대 1에 있는 원반을 막대 3으로 이동한다. 

 

 

이를 일반화하면

 

작은 원반 n-1을 막대 A에서 B로 이동 --> 큰 원반을 A에서 C로 이동 --> 작은 원반 n-1개를 B에서 C로 이동 

 

하는 과정이다. 

 

 

#include <stdio.h>

void HanoiTower(int num, char from, char by, char to)
{
    if(num==1)
    {
        printf("원반 1을 %c에서 %c로 이동 \n", from, to);
    }
    else
    {
        HanoiTower(num-1, from, to, by);
        printf("원반 %d를 %c에서 %c로 이동 \n", num, from, to);
        HanoiTower(num-1, by, from, to);
    }
}

int main(void)
{
    HanoiTower(3,'A','B','C');
    return 0;
}​