재귀(순환) 알고리즘

🟩 알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태

반복문을 사용하는 코드는 항상 재귀함수를 통해 구현하는 것이 가능하며, 그 반대도 가능하다.

재귀 함수를 작성할 때는 함수 내에서 다시 자기 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료조건이 꼭 포함 되어야한다는 부분을 인지하고 작성하면 무한루프를 방지 가능

 

🟩 for, while문 등 반복문과 비교하면 처리에 시간이 오래 걸리고 메모리 소모를 많이 한다.

스마트하게 프로그램을 작성할 수 있을 때만 사용해야 하는 기법

 

🌟 예1. 카운트다운

🌟 예2. 구구단 출력

🌟 예3. 팩토리얼

#include <stdio.h>

int factorial(int n) {
	printf("factorial(%d)가 호출되었습니다.\n", n);
	if (n == 0) {
		// 0의 계승은 1이므로 1을 반환하여 재귀 호출을 종료
		printf("factorial(0)이 1을 반환했습니다.\n");
		return 1;
	}
	else {
		int retVal = n * factorial(n - 1);
		printf("factorial(%d)가 %d를 반환했습니다.\n", n, retVal);
		return retVal;
	}
}

int main(void) {
	int ans;

	ans = factorial(5);
	printf("%d\n", ans);

	return 0;
}