열혈 자료구조 - 재귀적 호출의 이해

 

 

 재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이고,

C언어는 이렇듯 중요한 재귀를 지원하는 언어이다.

 

재귀함수의 기본적인 이해

 

재귀함수란 무엇인가?

재귀함수란 다음과 같이 함수 내에서 자기 자신을 다시 호출하는 함수를 의미합니다.

 

void Recursive(void)
{
    printf("Recursive call! \n");
    Recursive();		// 나 자신을 재호출한다
}

 

 

위 형태의 함수가 재귀호출이다.

그렇다면 재귀 호출은 어떻게 이해해야 할까?

 

 

다음 그림과 같은 구조는 매우 단순해 보이지만,

그림 내용대로 재귀함수를 이해하는 것이 여간 쉬운 일은 아니다.

 

그렇다고 위 그림이 재귀호출에 대해서 잘못 설명하고 있다거나 하지는 않는다.

 

해당 함수는 완료되지 않은 함수를 다시 호출하는 것이 가능한 것이 이론이다.

다음과 같은 말이 그럼 조금 더 이해 가능한 그림 구조로 바꿔보자

 

 

 

 Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면,

Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다.

 

위 문장의 내용은 재귀적인 형태의 함수호출이 가능한 이유를 충분히 설명하고 있다.

실제로 함수를 구성하는 명령문은 CPU로 이동이 되어서(복사 되어서) 실행된다.

이 명령문은 얼마든지 CPU로의 이동(복사)가 가능하다.

 

따라서 Resursive 함수의 중간쯤 위치한 명령문을 실행하다가

Recursive 함수의 실행을 완료하지 않은 상태에서 다시 Resursive 함수의 앞 부분에 위치한 명령문을 

CPU로 이동시키는 것은 문제가 되지 않는다.

그래서 재귀적인 형태의 함수호출이 가능한 것이다.

 

만약 다음과 같은 탈출 조건과 호출 조건을 가진 함수코드가 있다고 가정해보자.

#include <stdio.h>

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


int main(void)
{
	recursive(3);
    return 0;
}

 

 

해당 함수의 호출 과정 및 반환, 탈출 조건 성립시 행동은 다음과 같다.

 

이렇듯 재귀함수를 정의하는데 있어서 탈출조건을 구성하는 것은 매우 중요한 일이다.

 

 

 

재귀함수의 디자인 사례

 

 

 재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기이다.

무엇보다도 재귀함수가 있기에 재귀적인 수학적 수식을 그대로 코드로 옮길 수 있다.

그럼 이러한 재귀함수의 특징을 보이기 위해서 팩토리얼 값을 반환하는 함수를 재귀적으로 구현해 보겠다.

정수 n의 팩토리얼은 다음과 같이 n!로 표기하며,

이에 대한 수식적 의미는 다음과 같다.

 

n! = n * (n-1) * (n-1) * (n-2) * (n-3) * . . . * 2 * 1

 

따라서 3! 은 3 * 2 * 1 이며, 5!은 5 * 4 * 3* 2 * 1이다.

이러한 구조는 재귀 함수로 구현이 가능하다.

 

팩토리얼은 0!이 1이므로

n이 0일 때, 0이 아닐 때의 경우를 생각해야 하며,

1을 곱하게 되면 탈출 조건이 되므로 즉시 탈출한다.

따라서 이제 위 식은 재귀함수를 이용해서 그대로 코드로 옮길 수 있다.

 

 인자로 전달된 정수의 팩토리얼 값을 반환하는 함수의 이름을 Factorial이라 할 때,

n이 1이상인 경우의 주식 n * f(n-1)은 다음과 같이 표현이 된다.

 

if(n == 0)
	return 1;

 

그리고 n이 0인 경우의 결과값 1은 다음과 같이 표현이 된다.

 

if(n == 0)
	return 0;

 

 

따라서 Factorial 함수에 0 이상의 값만 전달된다는 가정을 하면,

위의 두 if문은 다음과 같이 하나의 if ~ else 문으로 묶을 수 있다.

 

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

 

 

해당 로직을 코드화 한 과정과

실행 결과는 다음과 같다.

 

#include <stdio.h>

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


int main(void)
{
	printf("1! = %d \n", Factorial(1));
	printf("2! = %d \n", Factorial(2));
	printf("3! = %d \n", Factorial(3));
	printf("4! = %d \n", Factorial(4));
	printf("5! = %d \n", Factorial(5));
	printf("9! = %d \n", Factorial(9));
}