[Data Structure] 재귀(Recursion)

● 재귀

재귀는 순환이라고도 불리며 함수가 자기 자신을 호출하여 문제를 해결하는 것을 의미합니다.

원래 함수를 정의할 때 A함수 안에 B함수를 정의하는 것은 불가능합니다. 그러나 A함수의 정의에 B함수를 활용할 수는 있습니다. 재귀는 여기서 A함수의 정의에 A함수를 활용하는 것이라고 할 수 있습니다.

 

재귀를 활용하는 대표적인 예시들이 있습니다. 

예를 들어 팩토리얼 함수의 구현입니다. n!을 계산하고자 할 때 우리는 이를 n * (n-1)!로 바꿔줄 수 있습니다. 그리고 우리는 또 (n-1)!을 (n-1) * (n-2)!로 바꿀 수 있습니다. 이를 코드로 구현하면 다음과 같습니다.

int factorial(int n) {
	
    if(n <= 1)
    	return 1;
    
    else
    	return (n * factorial(n-1));
}

 

재귀 함수의 호출 원리는 같은 함수가 여러 번 도는 것이 아니라 재귀로 호출될 때마다 해당 함수의 복사본을 만들어 그 속에서 계속 호출을 하는 것입니다. 예를 들어 5!을 보고 싶으면 먼저 매개변수 자리에 5를 넣어서 실행을 하면 factorial(4)에 대해서부터 재귀로 호출됩니다. 그럼 1까지 총 4개의 factorial 함수의 복사본이 만들어지게 됩니다. 결과적으로는 5를 매개변수로 했을 때의 호출을 딱 한 번인 것입니다. 이후의 4부터 1까지는 5가 매개변수인 factorial함수가 아니라 새로 생긴 복사본에 각자의 매개변수를 넣은 경우이기 때문입니다.

 

그러나 재귀 함수도 무한히 반복할 수 없기 때문에 탈출 조건이 필요합니다. 그 탈출 조건이 바로 조건문과 return문입니다.재귀 함수는 결국 범위를 정해두고 특정 횟수만큼 함수를 복사하고 값을 내기 때문에 반드시 횟수를 다 채우면 함수를 빠져나가게 해야 합니다.

재귀 함수는 함수 호출 순서가 정해져 있습니다. 비유하자면 마치 스택의 push, pop과 같습니다.

void Rec(int n)
{
	if (n <= 0)
		return;
	printf("Rec(%d)\n", n);		// 1번 출력문
	Rec(n-1);
	printf(“Rec(%d) done!\n”, n); 	// 2번 출력문
}

예를 들어 다음과 같은 함수가 있습니다. n의 자리에 3을 넣는다면 일단 1번 출력문에서는 3이 출력될 것입니다. 그러나 2번 출력문 이전에 재귀 함수가 존재하기 때문에 이제는 얘기가 달라질 것입니다. 

그렇다면 3이 2번 출력문으로 가기 전에 Rec(2)에 대한 복사본이 만들어져 1번 출력문에 2가 들어가는 게 우선이 될 것입니다. 그런 다음, 2가 2번 출력문에 가기 전에 Rec(1)이 먼저 오기에 1번 출력문에 1이 들어가는게 우선이 될 것입니다. 마지막은 Rec(0)이고 이는 그대로 return 되어 재귀에서 빠져나올 것입니다. 재귀에서 빠져나오는 방향이 0->1->2->3이기 때문에 2번 출력문은 1부터 순서대로 적힐 것입니다. 

다른 예시로는 피보나치 수열이 있습니다. 피보나치수열은 이웃하는 두 숫자를 더하여 그다음 숫자가 되게 하는 수열입니다. 이를 일반화시키면 수열의 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 BSearch(int arr[], int first, int last, int target) {
	int mid;
    
    if(first > last)
    	return -1;
    
    mid = (first+last) / 2;
    
    if(target == arr[mid])
    	return mid;
    
    else if(target < arr[mid])
    	return BSearch(arr, first, mid-1, target);
    else
    	return BSearch(arr, mid+1, last, target);
}

기존과 매개변수가 바뀌었습니다. 이유는 지속적으로 바뀌는 first와 last 때문에 재귀를 시켜주기 위해서 이들을 직접적으로 조작해 줄 필요가 있기 때문입니다. 

먼저 탈출 조건이 필요합니다. 기존에 알고리즘에서는 while문의 조건을 first <= last로 했기 때문에 탈출 조건은 이와 반대로 적으면 됩니다. 

그다음은 반복문을 사용하지 않기 때문에 기존에 반복문 안에 적었던 조건문을 적어주면 됩니다. 그러나 재귀를 해야 하는 위치는 target이 arr[mid]와 다른 경우이기 때문에 그것에 해당하는 두 경우에 대한 재귀 함수 호출을 해주면 됩니다.

 

---

지금까지 재귀의 개념과 재귀 함수, 그리고 재귀 함수를 이진 탐색에 적용해 봤습니다.