[알고리즘] 재귀 - 팩토리얼

재귀 - 팩토리얼

재귀함수, 제대로 이해하려면 제일 어렵다고 생각한다.

사실 과제나 개발만하다가 알고리즘을 시작한지 얼마안되서 나도 헷갈리는 부분이 많다.

그러나 심화된 문제일수록 재귀함수의 적절한 쓰임이 중요하며

자칫 잘못해서 재귀함수를 사용 할 경우 일반적인 함수를 사용할 때 보다

연산의 시간이 더 길어 지거나 스택 오버플로우가 발생하므로 

정확한 이해가 동반되어야한다.

그럼 기초적인 예제를 통하여 재귀함수를 이해해 보도록하자.

  팩토리얼, 피보나치, 하노이탑..

이 3개의 문제는 재귀함수를 설명하는 대표적인 예제라고 할 수 있다.

그 중 팩토리얼을 먼저 풀어보도록 하겠다.

팩토리얼은 N!으로 표기되며 1부터 N까지의 수를 모두 곱하는 연산이다.

예를 들어 4!는 1X2X3X4 를 나타내며, 

팩토리얼은 고등학교 때 배웠듯이 경우의 수를 계산하거나

더 나아가, 알고리즘의 성능을 분석할 때 사용된다.

1. 일반적인 팩토리얼

#include<stdio.h>
 
int factorial(int num);
 
int main() {
    int num, result;
 
    scanf_s("%d", &num);
    result = factorial(num);
 
    printf("%d\n", factorial(num));                                                                         
 
    return 0;
}
 
int factorial(int num) {
    int i,result=1;
 
    for (i = 1; i <=num; i++) {
        result = i*result;
    }
 
    return result;
}
 

위의 예제는 일반적인 팩토리얼이다.

사용자로부터 팩토리얼에 들어갈 n값을 입력받고 이를 파라미터로 하는

팩토리얼 함수를 사용하여 계산을 수행한다.

이는 다음과 같은 정의에 의하여 반복문으로 만들어진 것이다.

팩토리얼

n!=1X2X3...Xn

2. 재귀 팩토리얼

#include<stdio.h>
 
int factorial(int num);
 
int main() {
    int num, result;
 
    scanf_s("%d", &num);
    result = factorial(num);
 
    printf("%d\n", factorial(num));                                                                         
 
    return 0;
}
 
int factorial(int num) {
    
    if (num == 1) {
        return 1;
    }
 
    return num * factorial(num-1);
}
 

다음은 재귀함수로 구현한 팩토리얼이다.

팩토리얼 함수의 리턴값에 주목하자. 함수 내부에서 자신을 다시 호출한다.

이와 같은 성질 때문에 자신을 다시 호출한다고 하여 재귀호출이라는 이름이 붙었다.

언뜻보면 헷갈리기 쉬운 공식이다. 그렇다면 이와같은 함수가 나오게된 식을 보도록하자

팩토리얼

1!=1

n>1 이면, n!=nX(n-1)!

다음과 같은 점화식으로 재귀함수가 만들어 지게되었다.

코드와 점화식을 비교해 보면 점화식의 내용을 

그대로 코드로 옮긴것 같은 느낌을 받는다.

재귀함수는 자신을 계속 호출하다가 종료 조건(if(num==1))을 만나면 

호출을 끝내고 값을 반환하게된다.

따라서, 재귀함수에는 반드시 종료조건이 들어가야하며, 이를 기준으로 연산을 수행한다.

위 예제의 연산의 수행 순서는 다음과 같다.

5!= 5X4!

= 5X(4X3!)

=5X(4X(3X2!))

=5X(4X(3X(2X1)))

재귀함수를 사용하는데 있어서 한가지 중요한 사실을 모든 재귀함수들은 

재귀함수를 사용하지 않는 일반적인 형태로 구현할수 있다는 것이다.

그럼에도 불구하고 재귀함수를 사용하는 이유는 보다 간결하며 쉬워진다는 것이다.

그러나 어디까지나 함수를 잘 이해할 때이므로 실제 사용에 앞서, 

보다 깊은 공부가 필요하다.