#8. 재귀 - Recursion

재귀의 이해

재귀란? 어떤 코드를 정의할 때 그 안에서 자기 자신을 참조하는 것을 말한다.

흐름 상 반복문과 혼동하거나 호출 구조를 헷갈리기 쉬운데,

 

먼저 반복문은 한번 함수 호출 시 그 함수의 본문을 계속적으로 반복하는 코드 동작이라 별개의 방식이고

호출 구조를 봤을 때 같은 자기 자신을 계속 호출하는 재진입의 구조로도 보이지만

정확하게는 원본 함수를 한번 호출하고, 같은 함수의 복사본을 계속 생성해내는 Copy&Paste -> Call 의 과정이라고 보는 것이 정확하다.

모든 코드 동작은 동작 시 컴퓨터에 메모리를 차지한다.

이때 재귀함수의 메모리 호출 - 해제 순서는

원본 - 복사본A - 복사본B - 복사본C ... 으로 소요됐을 경우

... - 복사본C - 복사본B - 복사본A - 원본 순으로 역방향으로 메모리 해제가 진행된다.

쉽게 풀어서, 제일 먼저 실행된 코드가 가장 마지막에 종료되는 스택(Stack) 구조라고 이해하면 될 것 같다.

 

재귀를 사용하려면 반드시 탈출 조건이 있어야 하는데 ( return )

이유는 당연하게도 탈출하지 못하는 코드는 무한루프에 빠지기 때문이다.

While에서도 반드시 return 혹은 break 등으로 탈출 코드를 작성하는 것과 같은 이유이다.

이 탈출조건을 작성할 때는 언젠간 참이 되어서 이 코드가 실행이 되는지를 확인해야 한다.

void Recursive(int num)
{
	if(num<=0) return;
	printf("Recursive call! %d",num);
	Recursive(num-1); 
}

이 예시코드 또한 처음 인자로 받은 num의 값으로 재귀함수를 시행하고 있다.

다만 탈출을 위해 if(num <= 0) return; 의 코드를 삽입하고, 재귀 호출 시 num의 값을 -1 을 시켜

언젠간 num 이 <= 0 이 되는 순간에 재귀를 종료하도록 하였다.

 

수학적 사례로 재귀를 이해하려면 가장 쉬운 예시로 팩토리얼(Factorial / n!)이 있다.

n! = n * n-1 * n-2 * .... * 1 의 구조인 공식으로

f(n) = n * f(n-1) 으로 정의한다.

공식을 보면 f(n) 을 정의하는데 있어 f(n)을 사용하는 재귀의 구조를 나타냄을 볼 수 있다.

이를 코드로 작성하면

if(n==0) return 1;
else return n* Factorial(n-1);

다음과 같은 형태가 될 것이다.

 

재귀의 활용

우리는 보통 함수를 이해하고자 할 때, 호출 관계와 호출 순서를 먼저 파악하고자 한다.

일반적인 함수에 있어서는 효과적인 방법이지만 재귀의 경우는 조금 특수한데,

사실상 많은 횟수가 시행될 수록 호출 순서를 파악하는 것이 불가능하기 때문이다.

 

이 예시로 그나마 파악하기 쉬운 피보나치 수열을 예로 들어본다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
//수열의 n번째 값 = n-1번째 값 + n-2번째 값

이와 같이 이전 두개의 인덱스를 더한 값이 다음 인덱스의 값이 되는 구조를 띄우는 수열이 피보나치 수열이다.

이를 코드로 구현하면

//n = 1 -> 0
//n = 2 -> 1
//other -> f(n-1) + f(n-2)

int Fibo(int n)
{
	if(n==1) return 0;
	if(n==2) return 1;
	else return Fibo(n-1) + Fibo(n-2);
}

이렇게 정의할 수 있겠다.

 

여기만 두고 생각했을 때, 처음 Fibo 함수가 호출되면서 인자로 10을 받았다고 생각해보자.

호출 순서 상 Fibo(10)이 먼저 호출되겠지만, 이를 알기 위해서는 Fibo(9) 와 Fibo(8)을 알아야 하고, 이 두가지를 알기 위해선 다시 Fibo(7)과 Fibo(6) 을 알아야 하는, 사실상 첫번째 인덱스까지 파고들어가야 원하는 값을 떠올릴 수 있다.

그나마 흐름을 파악하기 쉬운 피보나치 수열임에도 이정도의 어려움이라면, 다른 재귀 함수들의 호출 순서 파악은 어느 정도의 난이도인지 감이 올 것이다.

 

함수의 흐름을 그림으로 그려 보았다.

이는 첫 Fibo 함수 호출에 인자로 7을 넣은 경우이다.

호출 순서는 함수 옆에 적어져있는 번호와 같다.

 

결론적으로, 재귀에 대해서 학습할 때는 호출 순서까지 파악하려고 들지 않아도 괜찮다는 것이다.

학습 순서를 따지자면

1. 문제 확인

2. 구조 파악

3. 코드 작성

까지만 진행해봐도 될 것이다.

 

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

이전에 배웠던 이진 탐색 알고리즘의 핵심으로는

1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인

2. 저장되지 않았다면, 탐색 범위를 반으로 줄여서 다시 탐색 시작

으로 말할 수 있다.

 

코드로 살펴보면

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;
	else if (target < ar[mid])
		return BSearchRecur(ar, first, mid-1, target);
	else 
		return BSearchRecur(ar, mid+1, last, target);
}

다음과 같다.

 

1번의 동작을 시행하기 위한 코드로는

mid = (first + last) /2;	
    
if(ar[mid] == target) return mid;

이 두가지가 있다.

처음 받은 배열의 중앙 인덱스 mid 를 먼저 특정하고, 그 ar[mid] 가 원하는 값 target인지 확인한다.

맞다면 return 후 코드 종료, 아니라면 이제 2번 단계가 될 것이다.

 

2번의 동작을 시행하기 위한 코드로는

else if (target < ar[mid])
	return BSearchRecur(ar, first, mid-1, target);
else 
	return BSearchRecur(ar, mid+1, last, target);

이 두가지의 else 문이다.

target 이 배열의 중앙값 ar[mid] 보다 작을 경우 mid 기준 왼쪽을 탐색하기 위해 first값은 그대로, mid -1 값을 last로 넣어준다.

반대의 경우도 같은 원리로 동작한다.