[백준 10872] 팩토리얼

 팩토리얼 문제는 나중에 나올 Dynamic Programming(= DP)로 푸는 것이 훨씬 효율적이지만, 문제가 속해있는 단계 자체가 재귀이고 \(n\)의 범위도 12까지이니 간단하게 재귀로 해결하자.

 

 재귀로 구현해야 할 것은 하나이다.

 어떤 자연수\(n\)이 있을 때, \(n! = n * (n - 1)!\)임은 자명하다.

 이것을 이용해서 재귀함수를 한번 작성해보면

 

이런 코드를 작성할 수 있다.

 

 물론 단순히 for문을 사용하여 팩토리얼을 구할 수도 있지만, 팩토리얼 같이 점화식이 존재한다면 재귀로 구할 수 있다는 점만 알고 넘어가자.

 점화식이 있는 문제에 대해선 나중에 나올 DP 파트에서 자세히 다뤄보겠다.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

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

int main()
{
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
	
    cout << fact(n);
	
    return 0;
}