Question

Give a recursive algorithm for finding whenever n! and m are positive integers.

Short answer

The recursive algorithm is,

procedure mod factorial (n,m : positive integers)

if n = 1 then

return 1

else

return (n.(mod facorial $\left(\mathrm{n}-1,\mathrm{m}\right)$))mod m

Step-by-step solution

 Step 1: Describe the given information

The objective is to write the recursive algorithm for n! mod m.

 Step 2: Give a recursive algorithm for computing n! mod m

Call the algorithm "mod-factorial" and the input are two positive integers n, and m .

In this algorithm, use the recursive algorithm for finding n! and just apply the operation at each step. This enables to calculate n! mod m without dealing with very large numbers, even if is excessively large.

procedure mod factorial (n,m : positive integers)

if n = 1 then

return 1

else

return (n.(mod facorial (n - 1 , m)))mod m

Therefore, the recursive algorithm is shown above.