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

문제풀이에 앞서서 재귀함수에 대해 간단히 알아보고자 한다.

재귀는 작은문제로 나눠서 동일한 알고리즘을 반복적으로 적용하여 작은문제를 해결한 뒤 큰 문제를 해결할 수 있을 때 사용한다.

재귀적 정의는 base case(재귀함수를 종료)와 inductive part(재귀함수를 호출)으로 구성된다.

재귀함수 작성 절차

더 작은 문제로 표현할 수 있는가?

문제를 직접 풀 수 있는 것이 어떤 경우인지 base case로 확인

그럼 위 작성절차에 따라 팩토리얼 함수를 재귀적으로 생각해보자.

팩토리얼 재귀함수
 
base case:
    n<=1 return 1
 
inductive part:
    return n*factorial(n-1);

이를 소스로 나타내면 아래와 같다.

int factorial(int n) {
 
    if(n<=1)    //base case
 
        return 1;
 
    else         //inductive part
 
        return n*factorial(n-1);
 
}

반복 / 재귀를 사용해야 할 때

사실 재귀함수는 반복문으로 구현할 수 있고 반복문으로 구현하는것이 조금이라도 더 효율적이기 때문에 반복문으로 구현하는 것이 성능상으로는 더 좋다. 하지만 문제에 따라 재귀적 구현이 더 간단하고 자연스러운 경우가 있으므로 문제에 따라 적절하게 사용하는 것을 추천한다.(분할정복등을 통해 시간복잡도를 줄일 수 있는 경우와 같은 특수 케이스는 제외)

 * 참고

재귀함수는 함수를 반복해서 호출하므로 함수 인자를 반복해서 생성하기 때문에 stack 메모리에 계속 할당하며 부가적인 오버헤드가 생긴다.