팩토리얼 계산하기

흠시 2018. 8. 17. 11:55

1 * 2 * .. * n 과 같은 꼴을 팩토리얼이라 하고, 기호로 n! 이라고 한다.

예를 들면, 1 * 2 * 3 = 3! 이다.

일반적으로 팩토리얼을 구하는 방법은 다음 두 가지 방법이 있다.

1. 반복문으로 구하기

int factorial(int n){
    int r, i;

    r = 1;
    for (i = 2 ; i <= n ; i++)
        r *= i;
    return r;
}

1부터 n까지 하나씩 r에 곱해준 뒤 r을 리턴한다.

2. 재귀적으로 구하기

int factorial2(int n){
    if (n == 1)
        return 1;
    else
        return n * factorial2(n - 1);
}

n! = n * (n-1)! 
   = n * (n-1) * (n-2)!
   = ...
   = n * (n-1) * (n-2) *  ... 1

위 식을 이용한 방법이다.

이 방법은 계속해서 함수를 호출하는데, 함수 호출 및 사용은 메모리의 '스택' 영역을 사용하기 때문에, 함수가 호출될 때마다 '스택' 영역에 메모리가 누적된다. 따라서 n이 커감에 따라 스택 오버플로가 발생할 수 있다.
한 가지 더. 위 함수를 조금 더 최적화 시킬 수 없을까? 재귀는 항상 함수를 계속해서 호출하며 진행하는 방식이므로, 스택 오버플로를 신경쓰지 않을 수 없다. 위 경우, factorial(n-1) 을 호출하고 끝나는 것이 아니라, factorial(n-1) 을 호출하고 factorial(n-1)이 진행된 뒤 리턴되는 값을 받아 n을 곱하고 그 값을 리턴해야 한다.
예를들어, 3 * factorial(2) 에서, factorial(2)으로 부터 리턴된 값을 2! 이라 하자. factorial(3) 안에서 factorial(2) 를 호출하여 리턴된 값 2!을 받고 3을 2!에 곱하여 리턴한다.
나도 처음엔 이게 당연한 재귀방법이고, 이게 이상한게 있나? 라고 생각했는데, 이를 좀 더 최적화 시킬수 있다고 한다. 아래와 같은 call 방식 (return 에다 재귀식을 쓰는 방식)

return n * factorial(n-1);
위와 같은 방식을 tail recursion 이라하고, 이를 최적화시키는 문제를 Tail Call Optimization 이라 한다
아래 참조한 링크에서는 전형적인 재귀 문제인 '피보나치수열' 을 가지고 Tail Call Optimization 를 진행하는 과정을 보여주는데, 꽤나 흥미롭다.
아직 잘 모르는 사람이 있다면 꼭 보시길.

재귀, 반복, Tail Recursion

https://homoefficio.github.io/2015/07/27/%EC%9E%AC%EA%B7%80-%EB%B0%98%EB%B3%B5-Tail-Recursion/