재귀 함수를 활용해 숫자의 계승(팩토리얼)을 계산하는 C++ 프로그램

계승(Factorial)이란?

음이 아닌 정수 n의 계승(factorial)은 n보다 작거나 같은 모든 양의 정수를 차례대로 곱한 값입니다. 수학 기호로는 n!처럼 느낌표를 붙여 표현합니다.

예를 들어 7의 계승은 다음과 같이 계산되며 그 결과는 5040입니다.

7! = 7 * 6 * 5 * 4 * 3 * 2 * 1
7! = 5040

그렇다면 C++에서 재귀(recursion)를 사용하여 어떤 숫자든 계승을 손쉽게 구하려면 어떻게 해야 할까요? 지금부터 전체 코드와 함께 살펴보겠습니다.

재귀를 이용한 계승 계산 코드

#include <iostream>
using namespace std;
int fact(int n) {
    if ((n==0)||(n==1))
    return 1;
    else
    return n*fact(n-1);
}
int main() {
    cout<<"Factorial of 5 is "<<fact(5)<<endl;
    cout<<"Factorial of 3 is "<<fact(3)<<endl;
    cout<<"Factorial of 7 is "<<fact(7)<<endl;
    return 0;
}

실행 결과

Factorial of 5 is 120
Factorial of 3 is 6
Factorial of 7 is 5040

코드 동작 원리

위 프로그램에서 fact() 함수가 바로 재귀 함수입니다. main() 함수는 계승을 구하고자 하는 숫자를 인자로 넘기며 fact()를 호출합니다. 이 과정은 다음 코드 조각에서 확인할 수 있습니다.

cout<<"Factorial of 5 is "<<fact(5)<<endl;
cout<<"Factorial of 3 is "<<fact(3)<<endl;
cout<<"Factorial of 7 is "<<fact(7)<<endl;

fact() 함수 내부 로직은 크게 두 부분으로 나뉩니다.

1. 기저 사례(Base Case)

입력값이 0 또는 1이면 fact()는 더 이상 자신을 호출하지 않고 즉시 1을 반환합니다. 이는 재귀 호출이 무한히 반복되는 것을 막아주는 종료 조건 역할을 합니다.

2. 재귀 사례(Recursive Case)

입력값이 그 외의 숫자라면 fact()는 n-1 값을 인자로 하여 자기 자신을 다시 호출하고, 그 반환값에 n을 곱합니다. 이 과정이 반복되면 최종적으로 다음과 같은 형태가 됩니다.

n*(n-1)*(n-2)*...*3*2*1 → 즉, n의 계승

이 핵심 로직은 아래 코드 조각에 잘 드러나 있습니다.

int fact(int n) {
    if ((n==0)||(n==1))
    return 1;
    else
    return n*fact(n-1);
}

정리

재귀를 활용하면 계승처럼 반복적인 구조를 가진 문제를 매우 직관적이고 간결한 코드로 표현할 수 있습니다. 다만 입력값이 커질 경우 호출 스택이 깊어질 수 있으므로, 실무에서는 반복문 방식이나 메모이제이션 같은 최적화 기법과 함께 고려하는 것이 좋습니다.