C++ 재귀 함수로 숫자의 계승(팩토리얼) 구하기 – 예제 코드와 동작 원리

음이 아닌 정수 n의 계승(팩토리얼, Factorial)은 n보다 작거나 같은 모든 양의 정수를 곱한 값입니다.

예를 들어 4의 계승은 다음과 같이 24입니다.

4! = 4 * 3 * 2 * 1
4! = 24

정수의 계승은 재귀(recursion) 방식 또는 반복(iteration) 방식으로 구할 수 있습니다. 이 글에서는 재귀 함수를 활용한 구현 방법을 살펴봅니다.

예제 코드

다음 프로그램은 재귀 함수를 사용하여 숫자의 계승을 구하는 방법을 보여줍니다.

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

실행 결과

Factorial of 4 is 24

코드 설명

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

cout<<"Factorial of "<<n<<" is "<<fact(n);

fact() 함수의 동작은 두 가지 경우로 나눌 수 있습니다.

• 종료 조건(Base Case): 입력값이 0 또는 1이면 1을 반환합니다. 재귀 호출이 무한히 반복되지 않도록 멈추는 역할을 합니다.
• 재귀 호출: 그 외의 경우에는 자기 자신을 n-1 값을 인자로 하여 다시 호출하고, 그 반환값에 n을 곱합니다.

이 로직은 다음 코드 스니펫으로 표현됩니다.

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

호출 흐름 예시

n이 4일 때 재귀 호출은 다음과 같은 순서로 진행됩니다.

fact(4) = 4 * fact(3)
fact(3) = 3 * fact(2)
fact(2) = 2 * fact(1)
fact(1) = 1  ← 종료 조건 도달

각 호출이 차례로 반환되면서 곱셈이 이루어지고, 최종적으로 4 × 3 × 2 × 1 = 24라는 결과가 출력됩니다. 이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도 역시 재귀 호출 스택 깊이 때문에 O(n)입니다.