Consider the following algorithm for determining

for non$-$negative

$.$

def pow$($x$,$ n$)$:

result $=1$

do n times:

result $*=$ x

return result

Provide pseudocode for a recursive implementation of the above algorithm.

How many multiplications does this algorithm perform? Justify your answer.

Provide pseudocode for a recursive algorithm that computes

with

multiplications.

Provide pseudocode for an iterative version of the

algorithm.