재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이다.
재귛마수란 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다.
void Recursive(){
printf("Recursive call!\n");
Recursive(); //나 자신을 재호출
}
완료되지 않은 함수를 다시 호출하는 것이 가능하다.
Recursive함수가 내부적으로 다시 호출이되면 복사본이 생긴다.
즉 함수가 호출되면 해당 함수의 복사본을 만들어서 실행하는 구조이다.
Recursive함수를 실행하는 중간에 다시 Recursive함수가 호출되면, Recursive함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다.
실제로 함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서) 실행이 된다. 그런데 이 명령문은 얼마든지 복사가 가능하다. 따라서 Recursive함수의 중간쯤 위치한 명령문을 실행하다가 (Recursive함수의 실행을 완료하지 않은 상태에서) 다시 Recursive 함수의 앞 부분에 위치한 명령문을 CPU로 이동시키는 것은 문제가 되지 않는다. 그래서 재귀적인 형태의 함수 호출이 가능한 것이다.
재귀함수에는 탈줄 조건이 필수 조건이다. 탈출조건이 없을시 무한루프에 갇힌다.
#include <stdio.h>
void Recursive(int num)
{
if(num <=0) //재귀의 탈출 조건
reutnr; //재귀의 탈출!
printf("Recursive call! %d \n", num);
Recursive(num-1); //재귀의 탈출을 위해 -1씩 감소
}
int main()
{
Recursive(3);
return 0;
}
================실행결과==================
Recursive call! 3
Recursive call! 2
Recursive call! 1탈출조건에 해당하는 행을 보면 전달인자가 0이하인 경우 함수가 종료되도록 정의되어있다.
재귀함수의 디자인 사례
팩토리얼
n! = n x (n-1) x (n-2) x ... x 2 x 1
따라서 3!은 3 x 2 x 1이고, 5!는 5 x 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)!
정수 n팩토리얼은 정수 n과 n-1 펙토리얼의 곱으로 표현이 가능하다.
즉 n=0일땐 1이고
n이 1이상일때는 n x (n-1)!이다.
즉 n이 0일때 재귀의 탈출 조건이 된다.
Factorial을 팩토리얼값을 반환하는 함수라 할때
if(n >=1 ) //n이 1이상일때
return n * Factorial(n-1);
if(n==0);
return 1;
이렇게 표현이 가능하다.
Fatorial함수에 0이상의 값만 전달된다는 가정을 하면, 위의 두 if문은 다음과 같이 if ~ else문으로 묶을 수 있다.
if(n==0)
retrun 1;
else
return n * Fatorial(n-1);
#include <stdio.h>
int Fatorial(int n)
{
if(n==0)
return 1;
else
return n * Fatorial(n-1);
}
int main()
{
printf("1! = %d \n", Fatorial(1));
printf("2! = %d \n", Fatorial(2));
printf("3! = %d \n", Fatorial(3));
printf("4! = %d \n", Fatorial(4));
printf("9! = %d \n", Fatorial(9));
return 0;
}
=============실행결과===================
1! = 1
2! = 2
3! = 6
4! = 24
9! = 362880Fatorial 함수의 정의 과정은 재귀함수를 구현하는데 중요한 모델이 된다.
피보나치 수열 :Fibonacci Sequence
피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열이다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ....
앞엣것 두 개를 더해서 현재의 수를 만들어가는 수열이다. 처음 두개의 수 0과 1이 주어진 상태에서 수를 만들어가게 된다.
즉 첫번째와 두번째 값 0과 1을 더해서 세번째 값 1이 결정된다.
두번째, 세번째 값 1과 1을 더해서 네번째값 2가 결정된다.
즉 수열의 첫번째와 두번째가 아닌 n번째 값은 다음과 같이 결정한다.
수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값
수학적으로
n= 1 일때 0
n= 2 일때 1
otherwise 일때 n-1 + n-2
이를 코드르 옮기면
int Fibo(int n)
{
if(n==1) //피보나치 수열의 첫번째 값을 요구하면,
return 0;
else if(n==2) //피보나치 수열의 두 번째 값을 요구하면
return 1;
else
return Fibo(n-1) + Fibo(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()
{
int i;
for(i=1;i<15;i++)
printf("%d , Fibo(i));
return 0;
}
=============실행결과=================
0 1 1 2 3 5 8 13 21 34 55 89 144 233재귀함수를 정의할 때 필요한 것은 동일한 패턴을 반복할 때 이다.
이진 탐색 알고리즘을 살펴보면 재귀적인 성격을 지니고 있다. 때문에 재귀적으로 정의가 가능하다.
1. 탐색 범위의 중앙에 목표 값이 저장되어있는지 확인
2. 저장되어있지 않으면 탐색 범위를 반으로 줄여서 다시 탐색 시작
탐색의 실패가 결정되는 시점
탐색 범위의 시작 위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우
즉 이것이 재귀함수의 탈출조건이 된다. 재귀함수의 탈출은 탐색 대상을 찾았거나, 탐색 대상이 배열에 존재하지 않는 경우에 이뤄지기 때문이다.
int BsearchRecur(int ar[], int first, int last, int target)
{
...
}
함수의 매개변수 선언이 이전에 정의한 BSearch함수와 차이가 있다. 이는 탐색의 범위를 줄여나가면서, 다시 말해서 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)
{
if(first >last)
return -1; //-1의 반환은 탐색의 실패를 의미
mid = (frist + last)/2; //탐색 대상의 중앙을 찾는다.
if(ar[mid] == target)
return mid; //탐색된 타겟의 인덱스 값 반환
}
마지막 반복패턴인 반으로 줄여서 다시 탐색을 한다 는 코드를 입력하면
int BsearchRecur(int ar[], int first, int last, int target)
{
if(first >last)
return -1; //-1의 반환은 탐색의 실패를 의미
mid = (frist + last)/2; //탐색 대상의 중앙을 찾는다.
if(ar[mid] == target)
return mid; //탐색된 타겟의 인덱스 값 반환
else if(target< ar[mid])
return BSearchRecur(ar, first, mid-1, target);
else
return BSearchRecure(ar, mid+1, last , target);
}
else if문과 else문에 있는 BSearchRecur 함수가 다시 탐색의 대상을 반으로 줄이는 것이 함수 호출문의 재귀의 핵심이다.
#include <stdio.h>
int BsearchRecur(int ar[], int first, int last, int target)
{
if(first >last)
return -1; //-1의 반환은 탐색의 실패를 의미
mid = (frist + last)/2; //탐색 대상의 중앙을 찾는다.
if(ar[mid] == target)
return mid; //탐색된 타겟의 인덱스 값 반환
else if(target< ar[mid])
return BSearchRecur(ar, first, mid-1, target);
else
return BSearchRecure(ar, mid+1, last , target);
}
int main()
{
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
탐색 실패하노이 타워는 재귀함수의 힘을 보이는 대표적인 예로 꼽힌다.
하노이 타워는 한 번에 하나씩 옮길 수 있다. 그리고 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.
즉 막대 A에서 C로 옮기기 위해서는 막대 B의 도움이 필요하다 .
일련의 과정을 반복하기 떄문에 재귀의 특징을 가지고 있다.
즉 일련의 과정을 파악하면된다.
하노이 타워의 반복 패턴을 보면
원반 을 전체 C로 옮기려면, 작은 원반을 먼저 B에 옮겨야 한다.
작은 원반들을 다 옮기고 A에서 C로 큰 원반을 옮기면된다.
그 후 B에있는 원반을 다시 C로 옮기면 된다.
즉 옮기는 방법을 정리하자면
1. 작은 원반 3개를 (맨아래 원반을 제외한 나머지 원반을) A에서 B로 이동
2. 큰 원반(맨 아래의 원반)1개를 A에서 C로이동
3. 작은 원반(B로 옮겨진 원반) 3개를 B에서 C로이동
위 과정을 일반화 한다면
1. 작은 원반 n-1개를 A에서 B로 이동
2. 큰 원반 1개를 A에서 C로이동
3. 작은 원반 n-1개를 B에서 C로 이동
이렇듯 원반 n개를 이동하는 문제는 원반 n-1개를 이동하는 문제로 세분화되고, 또 원반 n-1개를 이동하는 문제는 원반 n-2개를 이동하는 문제로 세분화 된다. 즉 원반 n개를 이동하는 문제는 결국 원반 1개를 이동하는 매우 쉬운 문제로 세분화가 된다.
즉 막대 A에서 꽂혀있는 원반 n개를 막대 C로 옮기는 과정은 다음과 같이 재귀적으로 구성이 된다.
1. 작은 원반 n-1개를 (맨 아래의 원반을 제외한 나머지 원반을) A에서 B로 이동
2. 큰 원반(맨 아래의 원반)1개를 A에서 C로 이동
3. 작은 원반(위의 1단계에서 옮겨진 원반)n-1개를 B에서 C로 이동
위의 결론을 코드르 옮겨보면
//from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
...
}
위 함수의 매개변수 선언이 의미하는 바는 다음과 같다.
num개의 원반을 by를 거쳐서 (by를 이용해서) from에서 to로 이동한다.
재귀함수를 정의하는데 있어서 반드시 생각해야 할 것은 재귀의 탈출조건이다. 그런데 n개의 원반이동이 n-1개의 원반이동으로 세분화 되어서 재귀를 구성하게 된 것이므로 탈출의 조건은 다음과 같다.
"이동해야할 원반의 수가 1개인 경우"
이동해야할 원반의 수가 1개이면 그냥 옮기면된다. 그래서 이것이 재귀의 탈출 조건이 된다. 위의 코드에 탈출조건을 삽입해보면
//from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
if(num==1) // 이동할 원반의 수가 1개라면
{
printf("원반 1을 %c에서 %c로 이동 \n ", from, to);
}
else
{
...
}
}마지막에 남는 원반은 가장 작은, 맨 위에 위치한 원반이므로 원반 1이 된다.
이번에는 원반 n개를 막대 C로 옮기는 세개의 과정중 첫번째 에 해당하는 코드를 추가해보면
"작은 원반 n-1개를 (맨 아래의 원반을 제외한 나머지 원반을) A에서 B로 이동"
여기서 주목할 것은 원래 원반 n개를 A에서 C로 이동하는 것이 목적인데, 이를 위해서 n-1개의 원반을 A에서 B로 이동해야 하는 사실이다.
//from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
if(num==1) // 이동할 원반의 수가 1개라면
{
printf("원반 1을 %c에서 %c로 이동 \n ", from, to);
}
else
{
HanoiTowerMove(n-1, from, to, by);
...
}
}위의 코드를 보면 to와 by의 전달인자가 바껴있는 것을 확인할 수있다.
즉 n개를 A에서 C로 이동하기 위해선는 n-1개를 A에서 B로 이동해야 하기 때문이다.
즉 n-1개는 C를 이용하여(C를 거쳐서) 최종적으로 B로 이동되는 것이다.
이제 두번째와 세번째에 해당하는 코드를 동시에 추가하면
"큰 원반(맨 아래의 원반)1개를 A에서 C로 이동"
"작은 원반(3단계중 1단계에서 옮겨진 원반)n-1개를 B에서 C로 이동.
//from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
if(num==1) // 이동할 원반의 수가 1개라면
{
printf("원반 1을 %c에서 %c로 이동 \n ", from, to);
}
else
{
HanoiTowerMove(n-1, from, to, by); //3단계중 1단계
printf("원반 %d을(를) %c에서 %c로 이동\n", num, from, to); //3단계중 2단계
HanoiTowerMove(n-1, by, from, to); //3단계중 3단계
}
}위의 코드의 1단계, 2단계 , 3단계를 세부적으로 살펴보면
1단계에서 전달인자가 바뀐이유는 n-1개의 원반을 A에서 시작해서 C를 걸쳐 B로 이동한다는 것이다.
2단계에서 n-1개의 원반들이 모두 B로 이동되었기 때문에 그냥 n을 A에서 C로 이동시키는 것이다.
3단계에서 n-1개의 원반들이 B에 있기 떄문에 B에서부터 A를 이용해 C로 모두 이동시키는 것이다.
이제 하노이 타워의 재귀함수를 이용해 예제를 만들면
#include <stdio.h>
//from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
if(num==1) // 이동할 원반의 수가 1개라면
{
printf("원반 1을 %c에서 %c로 이동 \n ", from, to);
}
else
{
HanoiTowerMove(n-1, from, to, by); //3단계중 1단계
printf("원반 %d을(를) %c에서 %c로 이동\n", num, from, to); //3단계중 2단계
HanoiTowerMove(n-1, by, from, to); //3단계중 3단계
}
}
int main()
{
//막대 A의 원반 3개를 막대 B를 경유하여 막대 C로 옮기기
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로 이동
하노이 타워의 문제를 재귀함수 기반으로 해결하였다.
'휴지통 > 자료구조-C' 카테고리의 다른 글
| 연결리스트2 (0) | 2021.02.13 |
|---|---|
| 링크드리스트1 (0) | 2021.02.12 |
| 배열 기반의 리스트(List)2 (0) | 2021.02.09 |
| 배열 기반의 리스트(List)1 (0) | 2021.02.08 |
| 자료구조와 알고리즘 이해 (0) | 2021.02.03 |
