DS06 - 재귀함수

재귀호출(Recursive Call)의 개념   

  재귀함수에 대한 설명은 링크에 있다.

http://0verc10ck.tistory.com/9

  링크를 누르고 이동하면 이 글이 나온다. 새로 열린 글에서 링크를 눌러도 또 다시 이 글이 나올것이다.

이처럼 재귀호출(Recursive Call)은 함수가 자기 자신을 호출하여 순환하여 수행되는 것으로 순환 호출 또는 Recursion이라고 한다.

함수에서 실행해아 하는 작업의 특성에 따라 재귀호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있다.

  그렇다면 어떤 경우에 재귀호출이 필요할까? 

프로그램을 실행하다가 어떤 작업이 필요하면 그 작업을 담당하고 있는 함수를 호출하여 처리하게한다.

재귀호출은 함수 입장에서 보면, 내가 나를 호출 하는 것이므로 현재 작업을 수행하기 위해 같은 유형의

하위 작업을 수행해야 한다는 것을 의미한다.

해결하려는 문제의 특성에 따라 문제를 한번에 해결하기 보다는 같은 유형의 하위 작업으로 분할하여 작은 문제 부터 해결하는 것이 효율적일 수 있다.

  한번에 해결 할 수 없는 현재 작업을 한단계 작게 분할한 하위 작업에 대하여 재귀호출하는 과정을 반복하다

보면 한번에 해결 할 수 있을 정도로 분할된 작업의 단위가 충분히 작아지는 단계가 되는데 이러한 단계를

베이스 케이스(Base Case)라고 한다.

베이스 케이스에서 구한 결과값을 함수가 반환하고 반환된 반환값은 재귀함수를 호출한 함수로 반환되는 과정을 반복하며 재귀호출이 역순으로 반복되어 결국 처음 문제의 답을 구하게 되는 것이 문제해결의 원리이다.

  

  다음 사진은 러시아의 전통 인형인 마트료시카(Матрёшка)이다.

가장 큰 인형을 열면 그안에 작은 인형이 들어있고 작은 인형을 열면 더 작은 인형이 안에 들어있는 구조이다.

사진속의 7개의 인형을 다시 하나로 합치려면 어떻게 해야할까?

1번 인형을 완성시키려면 2번인형이 완성되어야 한다. 2번인형이 완성되려면 3번인형이 완성되어야 하고

3번인형은 4번인형이 4번은 5번 5번은 6번 6번은 7번인형이 완성되어 있어야 한다.

이런식으로 각 인형은 자기 자신을 완성하기 위해 필요한 인형을 완성하기 위한 재귀적 호출을 실행하고 이때의 베이스 케이스는 이미 완성된 가장 작은 단위의 인형인 7번 인형이 된다.

7번 인형부터 재귀 호출자를 반환하며 재귀호출을 역순으로 따라가다보면 인형을 하나로 합칠 수 있다.

이러한 과정이 재귀 호출 과정이다.

재귀호출 - 팩토리얼(Factorial)      

  대표적인 재귀호출에는 팩토리얼(Factorial)이 있다.

n에 대한 팩토리얼은 1 ~ n까지의 모든 자연수를 곱하는 연산이다.

n! = n * (n - 1)!을 구하기 위해서는 (n - 1)!의 값을 알아한다.

따라서 (n - 1)! = (n - 1) * (n - 2)!을 구해야 하는데 그려려면 (n - 2)!의 값이 필요하므로 

(n - 2)! = (n - 2) * (n - 3)!의 값을 구해야 하고 또 다시 (n -3)!의 값을 구해야 한다.

이와 같이 현재 필요한 팩토리얼을 구하려면 하위값에 대한 팩토리얼을 구하는 작업을 베이스케이스인 1!까지

반복해야 한다.

다음은 재귀호출과 반복문을 이용한 팩토리얼 함수이다.

//재귀함수
long int fact(int n)
{
   if(n <=1)
     return(1);

   else
     return (n * fact(n-1));
}

//반복문
long int fact(int n)
{
   int i, f = 1;
   if(n <=1)
     return(1);

   else
   {
        for(i = n; i >= 0; i--)
        {
             f = f *i;
        }
        return f;
   }
}

재귀호출 - 하노이탑(Hanoi Tower) 

  팩토리얼 함수의 경우 반복문을 통해서도 구현 할 수 있었지만 복잡한 재귀 구조의 문제는 재귀호출을 사용해야 풀 수 있다. 대표적인 예가 하노이탑(Tower of Hanoi)퍼즐 이다.

  하노이탑의 목적은 세 개의 기둥에서 첫번째 시작봉에 있던 원판을 세번째 목적봉으로 옮기는 것이다.

이때 주의할 점은 크기가 큰 원판은 자기 자신보다 작은 원판 위에 놓일 수 없다는 점이다.

위의 사진은 원판 4개로 이루어진 하노이탑 퍼즐을 푸는 방법이다.

다음은 재귀호출을 이용하여 원반이 3개일 때 하노이탑을 구현한 프로그램과 그 결과값이다.

#include 

void hanoi(int n, int start, int work, int target);

int main(void) 
{
	hanoi(3, 'A', 'B', 'C');
}

void hanoi(int n, int start, int work, int target)
{
	if(n == 1)
		printf("%c 에서 원반 %d를(을) %c로 옮김\n", start, n, target);
		
	else
	{
		hanoi(n-1, start, target, work);
		printf("%c 에서 원반 %d를(을) %c로 옮김\n", start, n, target);
		hanoi(n-1, work, start, target);
	}
}

/*
A 에서 원반 1를(을) C로 옮김
A 에서 원반 2를(을) B로 옮김
C 에서 원반 1를(을) B로 옮김
A 에서 원반 3를(을) C로 옮김
B 에서 원반 1를(을) A로 옮김
B 에서 원반 2를(을) C로 옮김
A 에서 원반 1를(을) C로 옮김
*/

재귀호출을 사용하면 반복문을 사용할 때 보다 간결하게 코드를 완성할 수 있다.

하지만 재귀호출을 잘못 사용하면 오히려 불필요한 반복을 수행하여 오히려 프로그램 수행 시간이 오래 걸릴 수 있다. 또한 베이스케이스가 없을 경우 재귀 호출을 무한 반복 할 수 있기 때문에 주의해야 한다.