재귀 팩토리얼

Coddy C++ 여정의 로직과 흐름 섹션에 포함된 레슨 — 56개 중 46번째.

숫자의 팩토리얼(계승)은 재귀의 동작을 보여주는 완벽한 예시입니다. n의 팩토리얼(n!로 표기)은 1부터 n까지의 모든 양의 정수의 곱입니다. 예를 들어, 5! = 5 × 4 × 3 × 2 × 1 = 120입니다.

팩토리얼이 재귀에 이상적인 이유는 자기 자신을 통해 정의될 수 있기 때문입니다: n! = n × (n-1)!. 즉, 5!을 계산하려면 5에 4!을 곱하고, 4!을 계산하려면 4에 3!을 곱하는 식입니다.

재귀 팩토리얼 함수는 다음과 같습니다:

int factorial(int n) {
    if (n <= 1) {           // 기저 사례: 0!과 1!은 모두 1입니다
        return 1;
    }
    
    return n * factorial(n - 1);  // 재귀 단계: n! = n × (n-1)!
}

기저 사례(base case)는 n이 1 또는 0에 도달할 때 재귀를 중단하고 1을 반환합니다. 재귀 단계에서는 현재 숫자에 다음으로 작은 숫자의 팩토리얼을 곱합니다. factorial(4)를 호출하면, 기저 사례에 도달할 때까지 연속적인 호출을 수행하여 4 × 3 × 2 × 1을 계산한 다음, 호출이 반환됨에 따라 모든 결과를 함께 곱합니다.

챌린지

쉬움

재귀 팩토리얼 함수를 구현하고 이를 사용하여 다양한 입력 값에 대한 팩토리얼을 계산하는 프로그램을 작성하세요. 이 챌린지는 함수가 기본 케이스(base case)에 도달할 때까지 수정된 매개변수로 자기 자신을 호출하는 방식인 재귀의 작동 원리에 대한 이해도를 테스트합니다.

다음과 같은 입력이 제공됩니다:

팩토리얼을 계산할 숫자를 나타내는 정수 n

프로그램은 다음을 수행해야 합니다:

정수 매개변수를 받고 정수를 반환하는 factorial이라는 이름의 재귀 함수를 생성합니다.
함수는 기본 케이스를 구현해야 합니다: 만약 n이 1보다 작거나 같으면, 1을 반환합니다.
함수는 재귀 단계를 구현해야 합니다: n에 n-1의 팩토리얼을 곱한 값을 반환합니다.
메인 함수에서 입력 값을 읽습니다.
입력 값을 사용하여 팩토리얼 함수를 호출합니다.
지정된 형식을 사용하여 결과를 출력합니다.

다음과 같은 정확한 출력 형식을 사용하세요:

Factorial of [n] is [result]

팩토리얼 함수는 매번 더 작은 값으로 자기 자신을 호출하여, 각 재귀 호출마다 기본 케이스에 가까워져야 함을 기억하세요. 기본 케이스는 n이 1 또는 0에 도달했을 때 멈춤으로써 무한 재귀를 방지합니다. 재귀 단계는 현재 숫자에 다음으로 작은 숫자의 팩토리얼을 곱하며, 함수 호출이 값을 반환함에 따라 최종 결과를 만들어 나갑니다.

치트 시트

n의 팩토리얼(n!)은 1부터 n까지의 모든 양의 정수의 곱입니다. 이는 재귀적으로 다음과 같이 정의될 수 있습니다: n! = n × (n-1)!

재귀 팩토리얼 함수:

int factorial(int n) {
    if (n <= 1) {           // 기저 사례: 0!과 1!은 모두 1입니다
        return 1;
    }
    
    return n * factorial(n - 1);  // 재귀 단계: n! = n × (n-1)!
}

기저 사례는 n이 1 또는 0에 도달할 때 재귀를 중단합니다. 재귀 단계는 현재 숫자에 다음으로 작은 숫자의 팩토리얼을 곱합니다.

직접 해보기

#include <iostream>
using namespace std;

// TODO: 여기에 팩토리얼 함수를 작성하세요

int main() {
    // 입력 읽기
    int n;
    cin >> n;
    
    // TODO: 팩토리얼 함수를 호출하고 결과를 저장하세요
    
    // 결과 출력
    cout << "Factorial of " << n << " is " << result << endl;
    
    return 0;
}