[자료구조] 재귀함수 - 팩토리얼

재귀함수의 예제는 다양하게 있다. 그 중에 팩토리얼, 피보나치 수열, 하노이 타워 정도 프로그래밍 해볼것이며 오늘은 팩토리얼에 대해 구현해보겠다.

 

재귀함수란 자기 자신을 참조하는 함수 이다. 자 바로 예를 들어보자.

 

n! 은 n 팩토리얼로 n x (n-1) x (n-2) x ... x 1 을 계산한다. 자 처음보는 경우 나라면 반복문으로 접근할 것 같다. 이런 식으로 말이다.

 

#include <stdio.h>

int Factorial(int n) {
	int sum = 1;

	for (int i = n; i > 0; i--) {
		sum *= i;
	}

	return sum;
}

 

하지만 우리가 배우고 있는 것은 재귀함수 이므로 자기 자신을 참조하게 프로그래밍 해보겠다.

 

#include <stdio.h>

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

 

 

return n * Factorial(n-1); 에서 자기 참조가 일어났다. 이러한 특성을 가진 함수를 재귀함수라고 하는 것이다.

비교적 반복문 보다 간단한 것을 알 수 있다.

 

다음 시간엔 재귀함수의 다른 예제들을 가지고 돌아오겠다. ㅂㅇㅂㅇ