Answer to Question #284825 in Discrete Mathematics for deerendra

Question

show that factorial function is promitive recursive

Answer 1

The factorial function defined as $fac:\N\to \N$

Such that $fac(n)=n!$

From the definition of the factorial, we have that:

$fac(n)= n!=\begin{cases} 1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \text{if } n=0\\ mult(n,fac(n-1))~~~\text{if } n>0\end{cases}$

Thus fac is obtained by primitive recursion from the constant 1 and the primitive recursive function mult.

Hence fac is primitive recursive.