[알고리즘]재귀함수

재귀 함수란?

문제 해결을 위해, 원래 범위의 문제를 더 작은 문제로 쪼개 하위문제를 해결함으로써, 문제를 해결해 나가는 방식을 말한다.

 

재귀 함수를 사용할 때 장점은, 코드가 간결하고, 오류 수정이 용이하다는 것이다.

단점은, 코드를 이해하기 어렵고,  수많은 중복호출이 발생해 저장 공간을 많이 필요하다는 것이다.

 

예시를 살펴보자.

int recursiveSum (int n) {
    if(n == 1) return 1;
    return n + recursiveSum(n - 1);
}    

이 recursiveSum 함수는, 1부터 n까지의 합을 구하는 함수를 재귀 호출을 이용해 구현한 것이다.

n = 5일 때, 아래와 같이 동작한다.

모든 재귀함수는 if (n == 1)과 같이,

더이상 쪼개지지 않는, 최소한의 작업에 도달에 도달했을 때, 답을 곧장 반환하는 조건문을 포함해야 한다.

이렇게 더이상 쪼개지지 않는 가장 작은 작업들을 재귀호출의 '종료 조건' 혹은 '기저 사례'라고 한다.