[알고리즘] 재귀 함수

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

 

재귀함수

재귀 함수란 자기 자신을 재참조 하는 방법이다.

이때 주의할 점은 함수를 작성 할때 종료 조건을 반드시 작성해야 된다.

만약 그렇지 않으면 무한 루프에 빠지게 되고 결국 메모리 부족 현상이 발생할 것이다.

 

---

 

팩토리얼

int factorial(int n) {
	int tmp = 1;

	for (int i = 2; i <= n; i++) {
		tmp *= i;
	}
	return tmp;
}

펙토리얼은 1부터 n까지 다 곱하면 쉽게 구할수 있다.

하지만 이것을 재귀함수로 표현하면 다음과 같이 된다.

 

 

int factorial(int n) {
	if (n == 1) return 1; // 종료 조건
	return n * factorial(n - 1);
}

 

factorial(n[n >= 1]) = n * factorial(n - 1)

 

 

---

 

소스코드

#define __main

#ifdef __main

#include <stdio.h>

int factorial(int n) {
	if (n == 1) return 1; // 탈출 조건
	return n * factorial(n - 1);
}

int main() {
	printf("%d", factorial(5));

	return 0;
}

#endif