Using pseudo-code, describe a recursive algorithm to find n! mod m, when m, n? Z+.

A recursive algorithm has a terminating condition and a recursive rule.

The function "facMod" will terminate with an output of 0 if m ≤ n, because m would be a factor of n!. It will terminate with an output of 1 if n < 2.

Otherwise, it is the product mod m of n and the "facMod" of n-1.

facMod (m, n) : = If (m ≤ n, 0, If (n < 2, 1, Mod (n*facMod (m, n-1), m)))

__

In this code, the If (a, b, c) statement returns b for a=true, otherwise it returns c. The Mod (a, b) statement returns a modulo b.