[Data Structures][02-2] 재귀의 활용

본 글은 윤성우의 열혈 자료구조 책을 읽고, 강의를 수강하고 복습한 것을 기록한 글입니다.

강의 교안 또한 참고하여 작성하였습니다.

(강의 교안의 경우 오렌지 미디어에서 다운로드할 수 있습니다)

---

목차
Chapter 02. 재 귀(Recursion)

Chapter 02-2: 재귀의 활용

- 피보나치 수열

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

 

---

재귀의 활용

피보나치 수열

이해

저자는 호출 순서보다 호출 관계에 더 집중하자고 한다.

하노이 타워의 경우는 호출 관계도 어려운데 호출 순서는 더더욱 어렵다고 한다.

예시로는 피보나치수열이 있다.

 

문제 해결의 논리를 정확하게 파악하고 그 부분을 정확하게 잡아서 해결해야 한다. 그것이 재귀 문제의 핵심 키이다.

 

피보나치 수열

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

 

피보나치 수열의 구성

수열의 n번째 값 = 수열의 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);
}

int main(void)
{
	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

 

각각의 숫자들의 관계에 집중하는 것이 중요하다, 관계에 집중하게 되면 재귀 함수를 이해할 수 있기 때문이다.

 

함수의 흐름

 

피보나치 수열에서 위와 같이 직접 값을 넣어서 호출 순서를 추적할 수 있겠지만 어려운 문제일수록 호출 관계조차 파악하기 힘들 수 있다. 따라서 문제가 있으면 재귀적 논리를 세우고 코드로 만들고 test case를 넣어봐야 한다. 이런 식으로 경험을 늘린다면 재귀적 사고를 늘릴 수 있을 것이다.

 

---

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

수학적으로 쉽게 재귀식을 구현하는 경우는 코드 구현이 쉬운 편이다.

이진 탐색 알고리즘 자체는 재귀적인데, 재귀 구현은 어려운 편이다.

 

이진 탐색의 알고리즘의 핵심

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;
        			
    mid = (first + last) / 2;	// 탐색의 대상에서 중싱에 해당하는 인덱스 값 계산
    if(ar[mid] == target)	// 타겟이 맞는지 확인!
    	return mid;
    . . . .
}

if문으로 탐색 대상이 있는지 없는지 확인한다. 

없다면 탐색이 계속되게 한다.

 

 

계속되는 탐색

int BSearchRecur(int ar[], int first, int last, int target)
{
	int md;
    if(first > last)
    	return -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);	// 뒷부분을 대상으로 재 탐색
}

탐색은 두 가지중 하나로 진행되게 된다. target이 mid인덱스의 값보다 작은 경우와 큰 경우이다.

위의 코드에서 변화된 값을 재귀 함수의 매개변수로 대입한 것을 확인할 수 있다.

 

---