Chapter 02. 재귀 (Recursion)

 

---

1. 함수의 재귀적 호출의 이해

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

void Recursive(void)
{
	printf("Recursive call");
	Recursive();
}

위의 소스코드를 확인하면, 함수의 종료가 이루어지기 전, 다시한번 Recursive 함수를 호출하는 것을 볼 수 있다.

즉, 계속해서 호출이 된다는 것이다.
하지만, 재귀 함수의 문제는 계속해서 호출되는 문제가 있다. 이런 문제는 Recursive 함수에 '재귀의 탈출조건' 이 없다는데 원인이 있다.

#include <stdio.h>

void Recursive(int num)
{
	if(num<=0)
		return;
	printf("Recursive call! %d \n", num);
	Recursive(num-1);
}

int main(void)
{
	Recursive(3);
	return 0;
}

Recursive call! 3
Recursive call! 2
Recursive call! 1

여기서의 재귀의 탈출 조건은 if 문이 담당하고 있다.

 

 1.1 재귀함수의 디자인 사례

재귀함수는 수학적 수식을 그대로 옮기는 것에 이점이다. 그런 특성으로 재귀함수의 특징을 보이기 위해, 팩토리얼 값을 반환하는 함수를 재귀적으로 구현해본다.

n! = n x (n-1) x (n-2) x (n-3) x . . . . x 2 x 1

n! = n x (n-1)!

 

#include <stdio.h>

int Factorial(int n)
{
	if(n==0)
	    return 1;
	else
	    return n * Factorial(n-1);
}

int main(void)
{
	printf("1! = %d \n", Factorial(1));
	printf("2! = %d \n", Factorial(2));
	printf("3! = %d \n", Factorial(3));
	printf("4! = %d \n", Factorial(4));
	printf("5! = %d \n", Factorial(9));
    
	return 0;
}

1!  =  1
2!  =  2
3!  =  3
4!  =  24
9!  =  362880

 

---

2. 재귀의 활용

재귀함수를 이용한 소스코드(문제)들을 아래에서 다룰 예정이다.

 2.1 피보나치 수열 : Fibonacci Sequence

피보나치 수열은 재귀적인 형태를 가지고 있는 대표적인 수열이다. 구성은 아래와 같다.

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

#include <stdio.h>

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

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

이 코드에서는 피보나치 수열의 15번째 까지 출력시키는 소스 코드이다.
소스코드는 함수 호출 순서는 필요없다.
재귀함수 자체에 대한 이해가 필요하다.

 

 2.2 이진 탐색 알고리즘의 재귀적 구현

Chapter 01 에서 만든 이진 탐색 알고리즘을 재귀적으로 변경해본다.

재귀적인 표현을 위해서는 동일한 패턴을 반복하는 것을 찾아야한다.

1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인
2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작

그리고 탐색의 실패가 결정되는 시점은 아래와 같다.

탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우

 

그렇다면 위의 정보를 가지고 함수를 채워나가야한다.

우선 기본적으로 이진 탐색 배열, 시작, 끝, 찾아야하는 값을 인자로 설정한다.

int BSearchRecur(int ar[], int first, int last, int target)
{
    if(first > last)
    	return -1;  // -1의 반환은 탐색의 실패를 의미
}

 

반을 줄여 다시 탐색을 해야하므로 중간값을 도출하고 다시 재귀함수로 넣는 알고리즘을 작성한다.

int BSearchRecur(int ar[], int first, int last, int target)
{
    int mid;
    
    if(first > last)
    	return -1;  // -1의 반환은 탐색의 실패를 의미
        
    mid = (first+last) / 2;
    
    if(ar[mid] == target)   // 탐색된 타겟의 인덱스 값 반환
        return mid;
    else if (target < ar[mid])
    	return BSearchRecur(ar, first, mid-1, target);  // last -> mid-1 로 변경
    else
    	return BSearchRecur(ar, mid+1, last, target);  // first -> mid+1 로 변경
}

int main(void)
{
    int arr[] = {1, 3, 5, 7, 9};
    int idx;
    
    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 7);
    if(idx == -1)
    	printf("탐색 실패\n");
    else
    	printf("타겟 저장 인덱스: %d \n", idx);
        
    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 4);
    if(idx == -1)
        printf("탐색 실패\n");
    else
        printf("타겟 저장 인덱스: %d \n", idx);
        
    return 0;
}

 

 

---

3. 하노이 타워: The Tower of Hanoi

하노이 타워는 우리가 잘 아는 게임 중 하나라고 생각하면 편하다.

하노이 타워는 아래와 같다.

A에서 C로 옮겨야하며, 원반은 하나씩만 옮길 수 있다.
그리고 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.

그렇기에 우리는 막대 B를 사용하여 C로 넘겨야한다.
우리는 재귀파트의 문제를 풀고있다. 그러면 우리가 해야할 것은 반복패턴을 찾아내는 것이다.

 

 3.1 하노이 타워의 반복패턴

위 그림을 보면서 5개의 원판이 있다고 생각해보자.
원판 전체를 C 로 옮기기 위해서는 1~4 까지의 원판을 B 막대에 두어야 한다.

그러면 원판 5를 C로 옮길 수 있고, 나머지 1~4의 원판도 C 막대로 옮기면 문제는 끝난다.

이걸 정리하면 아래의 내용과 같다.

1. 작은 원판 4개(맨 아래 원판을 제외한 모든 원판)를 A에서 B로 이동.
2. 큰 원판(맨 아래의 원판) 1개를 A에서 C로 이동
3. 작은원판(B로 옮겨진 원판) 4개를 B에서 C로 이동

간략화
1. 작은 원판 n-1개를 A에서 B로 이동.
2. 큰원판 1개를 A에서 C로 이동.
3. 작은 원판 n-1개를 B에서 C로 이동

 

이를 보고 우리는 이동과정을 전부 보여주는 함수를 선언해야 한다.(여기서는 num을 3으로 설정했다.)

#include <stdio.h>

/*
HanoiTowerMove 함수
인자: num은 원판의 총 갯수를 넣고 from, by, to 직관 적인 이름대로 작성한다.
기능: 하노이 게임의 원판이 이동할때에 
*/
void HanoiTowerMove(int num, char from, char by, char to)
{
    if(num ==1)
    {
        printf("원판1을 &c에서 %c로 이동 \n", from, to);
    }
    else
    {
        HanoiTowerMove(num-1, from, to, by); 
        // 1단계: n-1개를 B막대로 보낸다.
        printf("원판%d을(를) %c 에서 %c로 옮긴다.", num, from, to);
        // 2단계: 5를 먼저 C로 넘긴다.
        HanoiTowerMove(num-1, by, from, to);
        // 3단계: B에 있는 n-1개를 C로 넘긴다.
    }
}

int main(void)
{
    HanoiTowerMove(3, "A", "B", "C");
    return 0;
}

원판1을 A에서 C로 이동
원판2을(를) A에서 B로 이동
원판1을 C에서 B로 이동
원판3을(를) A에서 C로 이동
원판1을 B에서 A로 이동
원판2을(를) B에서 C로 이동
원판1을 A에서 C로 이동

위와 같은 결과 값을 확인할 수 있다.

반복의 특성을 간략하게 확인하면 이를, 적용시킬 수 있다.