2강은 재귀다. 재귀 함수는 자기가 자신을 호출하는 것이다.
이....이게 뭔소리지??
일단 코드를 보고 이해해보자.
---------------------------------------------------------------------------------
#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;
}
---------------------------------------------------------------------------------
재귀 함수는 탈출 조건이 반드시 있어야 한다. 그렇지 않으면 무한루프에 빠질테니...;;
이번엔 재귀 함수를 이용해서 팩토리얼을 구해보자.
1. 재귀 함수를 이용한 팩토리얼
팩토리얼이란??
4! 이면 4 x 3 x 2 x 1 을 하는 것이다.
이걸 다르게 보면 n! = n x (n-1) x (n-2) x ..... x 2 x 1 이고,
이걸 압축해 보면 n! = n x (n-1)!
그리고 0! 은 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("9! = %d \n", Factorial(9));
return 0;
}
---------------------------------------------------------------------------------
너무 간단한가? ㅡㅡ;;; 하긴 나도 책에 있는 것을 복습 차원에서 또 쓰는 것이니....;;
소스코드를 베껴 쓰기보단 재귀 함수를 어찌 활용하는지 과정이 더 중요하다.
이번에는 피보나치 수열을 재귀 함수로 표현(?) 해보자.
먼저 피보나치 수열의 패턴을 생각해보자.
피보나치 수열이란?
첫째값과 둘째값을 더해서 셋째값을 구하고 한칸씩 이동하여 계속 반복하는 것이다.
이걸 식으로 나타내면
수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값
이걸 소스코드로 표현해보면.
--------------------------------------------------------------------------------
#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;
}
---------------------------------------------------------------------------------
2. 이진 탐색을 재귀 함수로 표현
이진 탐색도 값을 찾을 때까지 계속 동일한 패턴으로 반복하는 것이니 재귀 함수로 표현할 수 있다.
그럼 반복 패턴을 정리해보자.
1. 탐색 범위의 중앙에 목표값이 있나?
2. 없으면 범위를 반으로 줄이고 찾을 때까지 반복
3. 시작 위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last 보다 커지는 경우 끝
이걸 소스 코드로 표현해보면
---------------------------------------------------------------------------------
#include <stdio.h>
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);
else
return BSearchRecur(ar, mid+1, last, 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, 2);
if(idx == -1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
return 0;
}
---------------------------------------------------------------------------------
3. 하노이 타워
하노이 타워는 3개의 기둥을 이용해 1번에 있는 탑을 3번의 탑으로 이동 시키는 것이다.
규칙은 작은 원반이 큰 원반 아래에 위치할 수 없고, 한번에 한개만 이동시킬 수 있다.
이 규칙을 지켜가며 생각해보자.
1. 1번 기둥에 있는 가장 아래에 있는(가장 큰) 원반을 3번 기둥으로 옮겨야 한다.
이건 역으로 n개의 원반 중 n-1개만큼 2번 기둥으로 옮겨야 한다는 뜻이다.
2. 제일 큰 원반을 1번에서 3번 기둥으로 이동
3. 이제는 2번 기둥에 있는 n개 원반 중 다시 n-1개의 원반을 1번 기둥으로 이동
4. 2번 기둥에 있던 제일 큰 원번을 3번 기둥으로 이동
이걸 계속 다 쌓을 때까지 반복~
n의 개수가 1이 되면 그것만 3번 기둥으로 옮기면 되니깐 n이 1이 될 때 탈출 조건
이걸 기반으로 소스 코드로 표현해 보자.
---------------------------------------------------------------------------------
#include <stdio.h>
void HanoiTowerMove(int num, char from, char by, char to)
{
if(num==1) // 이동할 원반의 수가 1개라면
{
printf("원반1을 %c에서 %c로 이동 \n", from, to);
}
else
{
HanoiTowerMove(num-1, from, to, by); // 3단계 중 1단계
printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to); // 3단계 중 2단계
HanoiTowerMove(num-1, by, from, to); // 3단계 중 3단계
}
}
int main(void)
{
// 막대A의 원반 3개를 막대B를 경유하여 막대C로 옮기기
HanoiTowerMove(3, 'A', 'B', 'C');
return 0;
}
---------------------------------------------------------------------------------
재귀 함수를 이용하고 활용하는 것은 많은 연습과 경험이 필요할 것 같다.
기억해야 할 점은 반복 패턴을 찾고, 탈출 조건을 만드는 것이다.
그럼 오늘 공부도 여기까지~
댓글 없음:
댓글 쓰기