Chapter 02. 재귀의 활용

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

재귀함수는 이해하는 것도 중요하지만 잘 정의하는 것도 중요합니다. 그리고 재귀함수를 잘 정의하기 위해서는 사고의 전환이 필요합니다.. 그래서 사고의 전환을 위한 연습을 진행하고자 합니다.

---

우선은 간단하게 피보나치 수열부터 시작합니다. 피보나치 수열은 재귀적은 형태를 띄는 대표적인 수열로서 다음과 같이 전개가 됩니다.

 

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

 

쉽게 설명하자면 앞에 것 두 개를 더해서 현재의 수를 만들어가는 수열입니다. 때문에 처음 두 개의 수 0과 1이 주어진 상태에서 수를 만들어 가게 됩니다. 따라서 수열의 n번 째 값은 다음과 같이 결정됩니다.

 

수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값

 

따라서 피보나치 수열의 n번째 위치의 값을 반환하는 함수는 수학적으로 다음과 같이 표현됩니다.

n 값	fib(n)
1	0
2	1
그 외	fib(n-1) + fib(n-2)

위에서 fib(n)은 피보나치 수열의 n번째 값을 의미합니다. 저는 여기서 한 번 수정을 거쳐서 다음과 같이 표현했습니다.

n 값	fib(n)
2 이하	n -1
그 외	fib(n-1) + fib(n-2)

그리고 이를 코드로 옮기면 다음 예제와 같이 됩니다.

//main.c 소스 파일로 저장
#include <stdio.h>

int Fibo(int num)
{
	if (num <= 2) return num - 1;
	else return Fibo(num - 1) + Fibo(num - 2);
}

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

	return 0;
}

/*
실행결과

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

*/

위 예제의 실행결과를 보면 Fibo 함수의 정의가 적절했음을 확인할 수 있습니다.

 

그런데 보통 우리는 소스코드를 다음과 같은 형태로 분석합니다.

 

"이 함수가 호출되고, 그 다음에 저 함수가 호출되면서, 마지막으로 요 함수가 호출이 되네." 

 

즉, 함수의 호출순서가 파악이 되지 않으면 코드를 이해했다고 생각하지 않거나 찜찜해 하는 경향이 있습니다. 그래서 위 예제의 재귀호출 함수의 호출 순서를 정확히 파악하려고 노력할지도 모릅니다. 하지만 그러지 않는 것이 좋습니다. 그런 과정으로 인해서 오히려 더 혼란스럽게 될 우려가 있습니다.

 

재귀호출 함수를 소개하면서 했던 말이 있습니다.

"재귀적인 수학적 수식을 그대로 코드로 구현할 수 있다." 

이는 재귀함수의 장점이자 특징입니다. 즉, 우리는 함수의 호출관계를 명확히 따질 필요없이 재귀적인 수학적 수식을 그대로 코드로 옮기기만 하면 됩니다. 재귀함수가 호출되는 과정을 모두 명확히 하기는 꽤 힘든 일입니다.

 

그래도 아직 찜찜한 사람을 위해서 위 예제의 재귀호출 함수가 어떻게 호출이 되는지 보이도록 하겠습니다.

//main.c 소스 파일로 저장
#include <stdio.h>

int Fibo(int num)
{
	printf("func call param %d\n", num);

	if (num <= 2) return num - 1;
	else return Fibo(num - 1) + Fibo(num - 2);
}

int main(void)
{
	Fibo(7);

	return 0;
}

/*
실행결과

func call param 7
func call param 6
func call param 5
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2
func call param 3
func call param 2
func call param 1
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2
func call param 5
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2
func call param 3
func call param 2
func call param 1

*/

위 예제를 보고 Fibo함수의 호출관계를 이해하기 수월하셨나요? 저는 이해하기를 포기했습니다. 그리고 그래도 됩니다. 어쩌면 재귀호출 함수의 호출관계를 명확히 하려 하는 것이 어리석은 일인지도 모릅니다.

---

이번에는 앞서 구현한 이진 탐색 알고리즘을 재귀함수 기반으로 재구현하고자 합니다. 이 알고리즘을 수식적으로 표현하기는 부적절하지만 알고리즘의 논리 자체는 재귀적이기 때문에 충분히 가능한 일입니다. 이진 탐색 알고리즘의 반복 패턴은 다음과 같습니다.

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

그리고 재귀함수의 탈출조건은 '탐색 범위의 시작위치가 끝 위치보다 커지는 경우'입니다.

다음은 제가 이진 탐색 알고리즘을 재귀함수로 구현한 것입니다.

//main.c 소스 파일로 저장
#include <stdio.h>

int BSearchRecur(int* arr, int first, int last, int target)
{
	if (first > last) return -1;

	int index = (first + last) / 2;
	
	if (arr[index] == target) return index;
	else
	{
		if (arr[index] < target) first = index + 1;
		else last = index - 1;
		return BSearchRecur(arr, first, last, target);
	}
}

int main(void)
{
	int arr[] = { 1, 2, 3, 7, 9, 12, 21, 23, 27, 32 };
	int len = sizeof(arr) / sizeof(arr[0]);
	
	int index = BSearchRecur(arr, 0, len - 1, 21);
	if (index == -1) printf("탐색 실패!\n");
	else printf("타겟 저장 인덱스 : %d\n", index);

	index = BSearchRecur(arr, 0, len - 1, 4);
	if (index == -1) printf("탐색 실패!\n");
	else printf("타겟 저장 인덱스 : %d\n", index);

	return 0;
}

/*
실행결과

타겟 저장 인덱스 : 6
탐색 실패!

*/

재귀함수는 함수 안에서 함수를 호출하는 구조를 가지고 있습니다. 그리고 위 함수는 배열을 인자로 받고 있습니다. 배열을 포인터로 받은 이유는 메모리 공간을 아끼기 위함입니다. 만약 다음과 같이 포인터의 형태가 아닌 함수 안에서 배열을 선언하는 식으로 매개변수를 받게 되면,

int BSearchRecur(int arr[], int first, int last, int target);

함수를 호출할 때마다 해당 배열이 계속 새로 선언되어야 할 것이고, 배열의 크기가 클 수록 메모리를 차지하는 양이 늘어날 것을 생각해서 포인터로 받았습니다. 포인터로 배열주소를 받게되면, 배열이 아무리 커도 함수를 호출할 때마다 배열의 시작주소를 저장할 int형 메모리 공간 하나만 할당하면 되기 때문에 메모리 공간을 훨씬 절약할 수 있습니다.

 

다음은 이 책에 소개된 구현 방법입니다.

//main.c 소스 파일로 저장
#include <stdio.h>

int BSearchRecur(int arr[], int first, int last, int target)
{
	int mid;
	if (first > last) return -1;

	mid = (first + last) / 2;
	
	if (arr[mid] == target) return mid;
	else if (target < arr[mid]) return BSearchRecur(arr, first, mid - 1, target);
	else return BSearchRecur(arr, mid + 1, last, target);
}

int main(void)
{
	int arr[] = { 1, 2, 3, 7, 9, 12, 21, 23, 27, 32 };
	int len = sizeof(arr) / sizeof(arr[0]);
	
	int index = BSearchRecur(arr, 0, len - 1, 21);
	if (index == -1) printf("탐색 실패!\n");
	else printf("타겟 저장 인덱스 : %d\n", index);

	index = BSearchRecur(arr, 0, len - 1, 4);
	if (index == -1) printf("탐색 실패!\n");
	else printf("타겟 저장 인덱스 : %d\n", index);

	return 0;
}

/*
실행결과

타겟 저장 인덱스 : 6
탐색 실패!

*/

코드는 제가 구현한 것과 같으나 매개변수의 배열을 포인터의 형태로 받고 있지 않습니다.