Review the definition of function of \(f\).

For a non-negative integer \(x\),

• \(f(0)=1\)
• \(f(k)=k \times f(k-1)\) for all positive integers \(k\)

The definition of \(f\) contains the function \(f\) it self; such a function is called a recursive function.

Computer programs are good at executing recursive function. You can just implement as defined, and you will get accepted for this problem.

Sample code (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;
}

If you observe the function \(f\), you may observe that \(f(x)=x!\) (factorial of \(x\)).

Bonus starts here.

Actually, it is not a good idea to implement any kind of recursive functions directly. Consider the following function \(g\).

For a non-negative integer \(x\),

• \(g(0)=0\)
• \(g(1)=1\)
• \(g(k)=g(k-1)+g(k-2)\) for all integers \(k \ge 2\)

Finding this \(g(80)\) will lead to TLE.

Implementation (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;
}

Instead, we can use a technique called memorized recursion. By recording \(g\) that we already known, we can sometimes avoid excessive recursive calls and speed up the program.
Sample code (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;
}

By the way, \(g(x)\) is a function that prints the \(x\)-th term of Fibonaci’s sequence.