[알고리즘 이론] 재귀함수

재귀란?

주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법

 

재귀함수

함수 내부에서 직간접으로 자기 자신을 호출하는 함수

'기본 부분(기저조건)+ 유도 부분(실행부분)' 로 구성

함수호출은 프로그램 메모리 구조에서 스택 사용 → 메모리 및 속도에서 성능저하 발생

재귀함수는 반복구조보다 간결하고 이해하기 쉽다.

 

예시(팩토리얼)

1. 재귀적 표현

기본부분(기저조건)
N<=1인 경우, n==1
유도부분
N>=1일 때, n ! =  n x (n-1)!

 

2. 재귀함수 코드

int factorial(int n) 
{
	if(n <= 1)		// 기저조건
    	return 1;
    
    else			// 유도부분
    	return n *= factorial(n-1);
}