Chapter 02 재귀

재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이고, C언어는 이렇듯 중요한 재귀를 지원하는 언어이다.

 

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

재귀함수는 종료조건을 반드시 넣어줘야 한다. 아니면 무한루프에 빠지게 된다.

 

(열혈 C에서 재귀함수를 설명하였으므로 나머지는 열혈 C를 참고하자.)

이것은 팩토리얼을 재귀함수로 구현한 것이다.

Factorial(int num)

{

     if (n == 0)

          return 0;

     else

          return n * Factorial(num-1);

}

 

복사의 개념으로 생각하자. 실제로 함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서) 실행이 된다.

 

02 - 2 재귀의 활용

 

함수를 잘 이해했다는 기준 : 호출관계 + 호출순서 그러나 재귀함수에선 호출순서를 파악하려고 하면 힘들다.

 

피보나치 수열: Fibonacci Sequence

피보나치 수열은 0 1 1 2 3 5 8 13 21 34 55 . . . . . 로 n - 2, n - 1 이 더해져 n 항이 생기는 것이다.

 

n = n - 1   +   n - 2

#include 

int Fibo(int n)
{

printf("func call param %d \n", n);

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

int main(void)
{
Fibo(7);
return 0;
}

참고로 재귀함수의 호출순서를 정리하는 것은 큰 의미가 없다 그러므로

문제 -> 재귀적인 논리 -> 코드로 옮김 -> 테스트

후 재귀 구현이 완료된 것이다. 재귀함수 자체를 이해하도록 하자.

 

 

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

수식적으로 표현하기는 부적절하지만 이 알고리즘의 논리 자체는 재귀적이기 때문에 충분히 가능하다.

대상을 찾을때 까지 동일한 패턴을 반복하는 것이므로 재귀적인 성격을 지녔다고 볼 수 있다.

 

1, 탐색 범위의 중앙에 목표 값이 저장되었는지 확인

2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색

#include 

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 (ar[mid] < target)
return BSearchRecur(ar, mid + 1, last, target);
else
return BSearchRecur(ar, first, mid - 1, target);
}

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;

}

 

 

02-3 하노이 타워: The Tower of Hanoi

하노이 타워

하노이 타워는 1883년도에 프랑스의 수학자에 의해서 처음 소개가 되었다.

여기에는 두가지 조건이 붙는다.

 

1. 한번에 하나의 원반만 옮길 수 있다.

2. 작은원반 위에는 큰 원반이 올 수 없다.

 

이 알고리즘은 재귀함수로 구현할떄 간단하다.

A, B, C 세개의 봉이 있고 원반이 n개라고 가정할떄,

 

1. 제일 큰 원반(n번째) 을 C로 옮겨야 한다.

(제일 큰 원반을 옮기기 위해선 나머지 작은 원반(n-1개)을 B쪽으로 옮겨야 한다.

2. n-1개의 원반을 B쪽으로 옮기기 위해선 n-1번째 원반을 제외한 나머지 n-2개의 원반을 C쪽으로 옮겨야 한다.

(C쪽으로 옮기기 위해선 나머지 다른 n-3개의 원반을 B쪽으로 옮겨야한다)

.

.

.

.

이렇게 재귀적 과정을 반복한다.

 

그러므로 식을 일반화 하면,

1. n번째 원반   A -> C        (4)

2. n-1개의 원반 A -> B     (1, 2, 3)

3. n-2개의 원반 A -> C      (1, 2)

4. n-3개의 원반 A -> B        (1)

 

여기에 일련의 규칙이 보이지 않는가?

결국 처음에는 4개의 원반을 옮기는 문제였지만 재귀적으로 풀어내면 3개의 원반, 2개의 원반, 1개의 원반을 옮기는 문제로 볼 수 있다.

이걸 코드로 구현하면 아래와 같다.

#include 

HanoiTowerMove(int n, char from, char by, char to)
{
if (n == 1)                  // 종료 조건 마지막에 제일작은 원반이 하나 있을 경우 그냥 옮기면 된다.
printf("원반1 을 %c 에서 %c로 이동 \n", from, to);
else
{
HanoiTowerMove(n - 1, from, to, by);
printf("원반%d을(를) %c 에서 %c로 이동  \n", n, from, to);
HanoiTowerMove(n - 1, by, from, to);
}
}

int main(void)
{
// 막대A의 원반 4개를 막대B를 경유하여 막대C로 옮기기
HanoiTowerMove(4, 'A', 'B', 'C');
return 0;
}