Question

Give pseudocode for a memoized algorithm that computes n factorial. You will want to think about the implementation of an appropriate data structure as well as a sentinel value for this problem.

Note: a memoized factorial algorithm is not considered dynamic programming, as factorial does not encounter repeated subproblems while recursing. However, memoizing this algorithm is the same process as memoizing a dynamic programming algorithm.

Answer 1

Pseudo - code :

memory ={}

fact(n):
    if n in memory:
        return memory[n]
    elif n == 0:
        return 1
    else:
        x = fact(n-1) * n
        memory[n] = x
        return x

a = fact(10)
b = fact(20)

print a,b

What we are doing here, is, we created a list named memory, in which its ith index store factorial of i. This will fulfill the desire of memoized algorithm of computing factorial.

To compute factorial we are using recursion here.

//x = fact(n-1)*n

above is the recursion step.

At the end function fact(n) returns factorial of n.

Like, if this helped :)