재귀 알고리즘이란

재귀란 러시아 인형을 예로 처음에는 하나의 큰 인형으로 시작해 점점 작아지며 제일 작은 인형까지 나타나는 것처럼
어떤 문제를 해결하기 위해 알고리즘을 설계할 때 동일한 문제의 조금 더 작은 경우를 해결함으로써 그 문제를 해결하는 것입니다. 문제가 간단해져서 바로 풀 수 있는 문제로 작아질 때까지 말이죠. 이런 테크닉을 재귀라고 합니다.

 

아래 코드는 순차곱셈을 구하기 위해 만든 프로그램입니다.
이처럼 순차곱셈의 결과를 재귀적으로 구하기 때문에 순차곱셈을 구하기 위한 프로그램에는 재귀 알고리즘이 포함되겠네요

#include<stdio.h>
//정수 n의 순차곱셈 값을 반환 
int factorial(int n){ //어떤 양의 정수 n 이 있을때, 1에서부터 n까지의 자연수를 모두 곱한 값을 팩토리얼이라고 함 
	
	if(n>0) 
		return n * factorial(n - 1);  
	else 
		return 1;
	
	
}
int main(void){
	
	int a;
	printf("정수를 입력하세요 : ");
	scanf("%d",&a);
	printf("%d의 순차곱셈 값은 %d입니다. \n",a,factorial(a));
	
	return 0; 
}

재귀에는 직접 재귀와 간접재귀가 있습니다.
factorial 함수는 그 내부에서 factorial 함수를 호출합니다. 이처럼 자신과 같은 함수를 호출하면 직접 재귀이고
함수 a가 b를 호출하고 다시 b가 a를 호출하는 구조로 이루어진다면 간접 재귀입니다.

재귀 알고리즘을 분석하기 위한
하향식 분석과 상향식 분석이 있습니다.

가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 조사해 가는 분석 기법을 하향식 분석이라고 하며
아래쪽부터 쌓아 올리며 분석하는 기법을 상향식 분석이라고 합니다.

꼬리 재귀의 제거, 재귀의 제거 같은 비재귀적 표현도 있습니다.