[c] 재귀 호출

재귀호출(recursive call)

재귀호출이란 함수 내부에서 함수가 자기 자신을 또다시 호출하는 행위를 의미하는데, 끝없이 반복할 수 있기 때문에 함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 한다. 

 

예를 들어 재귀 호출을 사용하지 않고 1부터 n까지의 합을 구하는 함수를 만들어 본다면, 아래의 코드와 같게 만들게 된다.

int sum(int n)	{
	int i;
    int result = 0;
 
    for(i=1 ; i<=n ; i++)	{
    	result += i;
    }
    return result;
}

여기서 재귀 호출을 사용하여 1부터 n까지의 합을 구하는 함수를 만들 때, 의사 코드(pseudo code)로 이를 작성해본다면 아래와 같다.

시작
1. n이 1이 아니면, 1부터 (n-1)까지의 합에 n을 더한 값을 반환한다.
2. n이 1이면, 1을 반환한다.
끝

이렇게 작성된 의사 코드를 재귀 호출을 이용해 구현한다면 아래와 같다.

int sum(int n)
{
	if(n==1)		//n이 1이면
    {
    	return 1;		//1을 반환한다.
    }
    return n + sum(n-1);	//n이 1이 아니면, n을 1부터 (n-1)까지의 합과 더한 값을 반환한다.
}

위의 예제에서 if문이 존재하지 않다면, 이 프로그램은 실행 직후 스택 오버 플로우(stack overflow)에 의해 종료될 것이다. 따라서 if 문처럼 재귀 호출을 중단하기 위한 조건문을 반드시 포함해야 한다.

 

재귀 호출은 비 재귀 호출보다 코드가 간결한 반면, 무한 재귀호출의 위험성과 성능 상의 문제를 가지고 있으며 실행 시간이 오래 걸린다는 단점을 가지고 있다.