Question

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

Answer 1

Explanation:

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.