関数 \(f\) の定義がどのようなものであったかを振り返ってみましょう。

非負整数 \(x\) に対し

• \(f(0)=1\)
• 任意の正整数 \(k\) に対し \(f(k)=k \times f(k-1)\)

このように、関数 \(f\) の定義に関数 \(f\) 自身を用いるような関数を 再帰関数 と呼びます。

再帰関数の実行はプログラムにとっては得意分野で、以下の通り定義通りに実装すればこの問題に正解できます。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

int f(int x){
  if(x==0){return 1;}
  return x*f(x-1);
}

int main(){
  int n;
  cin >> n;
  cout << f(n) << "\n";
  return 0;
}

なお、関数 \(f\) を観察すると、 \(f(x)=x!\) ( \(x\) の階乗) となることが分かります。

以下、おまけです。

実は、すべての再帰関数を定義通りに実装すれば良いというわけでもありません。以下のような関数 \(g\) を考えてみましょう。

非負整数 \(x\) に対し

• \(g(0)=0\)
• \(g(1)=1\)
• 任意の整数 \(k \ge 2\) に対し、 \(g(k)=g(k-1)+g(k-2)\)

この \(g(80)\) を求める際に、定義通りに実装しても TLE してしまいます。

実装(C++):

#include<bits/stdc++.h>

using namespace std;

long long f(long long x){
  if(x==0){return 0;}
  if(x==1){return 1;}
  return f(x-2)+f(x-1);
}

int main(){
  cout << f(80) << "\n";
  return 0;
}

そこで、 メモ化再帰 というテクニックがあります。再帰中に既に分かっている \(g\) の値をメモしておくことによって、余分な再帰呼び出しを行わずに計算を高速化することができることがあります。
実装例(C++):

#include<bits/stdc++.h>

using namespace std;

vector<long long> mem;
long long f(long long x){
  if(mem[x]!=-1){return mem[x];}
  if(x==0){return 0;}
  if(x==1){return 1;}
  mem[x]=f(x-2)+f(x-1);
  return mem[x];
}

int main(){
  mem.resize(85);
  for(auto &nx : mem){nx=-1;}
  cout << f(80) << "\n";
  return 0;
}

なお、 \(g(x)\) は フィボナッチ数列 の第 \(x\) 項を出力する関数です。