재귀함수란?

오늘 공부한 파트는 재귀이다. 팩토리얼과 피보나치 수열과 같이 간단한 재귀를 활용한 문제들이 많은 것도 맞지만, 이진 탐색과 같은 재귀함수를 활용하여 풀 수 있는 알고리즘들도 존재하기에 재귀는 알고리즘 내에서 굉장히 중요하다는 것을 알아야한다.

재귀함수란?
: 함수 내에서 자기 자신을 다시 호출하는 함수

ㅇvoid recursion(void)
{
	printf("안녕하세요. 제 velog에 오신것을 환영합니다.\n");
    recursion();
}

이렇듯, 논리적으로 재귀를 이해할 수 없어 보일 수 있지만, 완료되지 않은 함수 내에서 그 함수를 다시 호출 할 수 있다. 그럼 위에 있는 코드를 수행하면 어떻게 될까? print문으로 나와있는 문장들이 계속 나오면서 무한루프를 돌 것이라고 볼 수 있다. 즉, 재귀함수를 활용하기 위해서는 우리는 '재귀의 탈출조건'을 활용해야한다.
대표적인 예시로 팩토리얼을 활용해보자

예시 1) 팩토리얼

팩토리얼 같은 경우의 식은 다음과 같다.

0! 이거나 1! 의 값은 모두 1이기 때문에, 우리는 0! = 1 이라는 것을 탈출조건으로 두고 함수를 작성할 수 있다. 다음 팩토리얼 코드를 작성해보겠다.

int Fact(int n)
{
	if(n == 0) 	return 1;
   	else 	return n * Fact(n - 1)
}

여기서 main 함수를 따로 구상해, fact를 가져와서 활용해보면 함수가 잘 적용되는 것을 확인할 수 있을 것이다. 여기서 우리가 중요하게 볼 점은 재귀의 탈출조건이다.

한 가지 예시만 더 보도록 하겠다.

이진 탐색 알고리즘

이진 탐색 알고리즘은 정렬되어있는 배열이라고 가정할 때, 탐색 범위의 중앙을 목표값과 비교하면서 점점 탐색 범위를 줄여나가는 알고리즘이다. 빅-오 표기법으로 나타내면 O(logn)으로 나타낼 수 있다. 위 이진 탐색 코드도 나타내보도록 하겠다. 위 코드는 윤성우의 '열혈 프로그래밍' 에서의 코드를 참고했다.

int SearchRecur(int ar[], int s, int l, int n)
{
	int mid;
    mid = (s + l) / 2; 
    
    if(s > 1) 	return -1;
    
    if(ar[mid] == n)	return mid;
    else if(n < ar[mid])
    	return SearchRecur(ar, s, mid - 1, n);
    else
    	return SearchRecur(ar, mid + 1, l, n)
}

위 코드에서 중요한 부분은, 재귀의 탈출 조건이다. 재귀의 탈출 조건은 s가 l보다 커지는 시점을 기준으로 했는데, 여기서 s(start)는 배열의 시작부분이고, l(last)은 배열의 끝부분이다. 즉, 범위를 중간으로 계속 나누면서 탐색을 하고 있는 중에 결국 찾지를 못해 s가 l을 넘어서는 순간 이 알고리즘은 종료하게 되어있다. 그리고 -1을 반환하면서 찾지 못했음을 보여주고 있다. 그리고, 중간값을 기준으로 찾고자 하는 값이 클때와 작을때를 경우로 나누어 재귀를 써서 시작을 중간값보다 크게 해서 시작하거나 끝을 중간값보다 작게 함으로써 계속 줄여나가는 것을 볼 수 있다.

이렇게 오늘 재귀의 기본 틀과, 재귀에서 중요한 부분들을 공부를 해 보았다. 사실, 재귀를 쓰는 것은 오히려 성능이 떨어지는 것을 보일 수도 있다. 다만, 하노이탑과 같은 대표적인 예시를 보면 재귀함수를 사용하면 쉽게 풀 수 있는 문제들도 있기에 알고리즘들을 해결하는 방법들 중에 하나로, 익숙해지는 것이 좋은 듯 하다. 다음은 하노이탑과 관련해서 백준 문제 해결을 한 후, 해설과 같이 오도록 하겠다.