재귀함수_팩토리얼 예제 [1/1]

저는 개인적으로 시작할 때 들었던 악명 높은 포인터도 어렵다고 느껴본적이 없는데.. 오히려 재귀함수가 제일 어려웠던 것 같습니다. 물론 원리를 알고 나니 그리 어렵지만은 않지만요. 재귀함수는 잘못하면 무한루프가 돌기 쉬우니 조심하셔야 합니다.

​

[ 재귀함수란? ]

• 말 그대로 함수 안에 자기 자신의 함수가 다시 있는 것을 뜻 함 (Recursion)
• 특정 조건을 만족시킬때까지 함수실행-함수실행-함수실행 형태로 같은 함수 반복 수행

​아래는 재귀함수에서 제일 흔한 예제인 팩토리얼 구현입니다.

• 5! = 5 * 4 * 3 * 2 * 1 == 120
• 3! = 3 * 2 * 1 == 6

---

 

아래 예제만 보면 굳이 재귀함수를 사용할 필요 없이 일반 반복문을 사용하면 충분해 보입니다만.. 같은 기능을 다른 범위나 다른 argument에 대해서 반복 수행하는 경우 재귀함수가 효과적일 수 있습니다. 아래의 퀵 정렬 예시를 보면 알 수 있습니다.

 

2019/12/09 - [C언어/알고리즘 및 자료구조] - 정렬알고리즘_퀵 정렬 [4/8]

 

 

모든 함수가 return을 기다리는 상태로 다음 함수로 들어가 있으니, 마지막 함수에서 빠져나와 값이 return 되면 각 함수들은 남은 return만 수행하면서 처음으로 돌아오게 됩니다.

​

함수끼리의 지역 변수는 공유가 되지 않기 때문에 포인터를 사용하지 않는 한 함수에서 이전 함수로 값을 전달하는 방법은 return밖에 없다는 점에 유의하고, 재귀함수에서 빠져나오는 조건만 잘 설정하면 됩니다. 사실 실전에서는 void 함수를 쓰고 포인터로 값을 변경해주는 방식이 더 쉽게 작성할 수 있습니다.

​

아래 재귀함수는 가장 처음에 0이 들어갈 때와, 재귀함수를 타고 들어가다가 0이 되는 경우를 구분하기 위해 조건이 (n - 1 > 0)이 되었습니다. 만약 조건을 ( n > 0 ) 으로 설정할 경우 같은 결과를 도출할 수 있지만, 가장 처음 제공된 n이 0일 경우 다르게 나올 수 있습니다.

 

#include <stdio.h>
int factorial_loop(int n);
int factorial_recursion(int n);

void main()
{

	printf("%d\n", factorial_loop(5));
	printf("%d\n", factorial_recursion(5));

}

/* 일반 루프문을 이용한 팩토리얼 계산 */
int factorial_loop(int n)
{
	int result = n;
	printf("%d ", result);
	for (int i = n - 1; i > 0; --i)
	{	
		printf("%d ", i);
		result *= i;
	}

	return result;
}

/* 재귀함수를 이용한 팩토리얼 계산 */
int factorial_recursion(int n)
{
	if (n - 1 > 0)
	{	
		printf("%d ", n);
		return factorial_recursion(n - 1) * n;
	}
	else
	{
		printf("%d ", n);
		return n;
	}
}