$1,$ Describe a recursive algorithm for finding the maximum element in an array, $A,$ of n elements. What is your running time and space usage?

$2,$ Draw the recursion trace for the computation of power$(2,5),$ using the traditional algorithm:

A trivial recursive definition follows from the fact that $x^n=x*x^{n-1}$ for $n>0.$

power$(x,n)=\{\begin{array}{ccc}1& if& n=0\\ x*power(x,& n-1)\text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\text{.}& \end{array}$

This definition leads to a recursive algorithm shown in Code Fragment $5\mathrm{.}8.$Code Fragment $5\mathrm{.}8$: Computing the power function using trivial recursion.

$3,$Draw the recursion trace for the computation of power $(2,18),$ using the repeated squaring algorithm, as implemented in Code Fragment $5\mathrm{.}9.$Code Fragment $5\mathrm{.}9$: Computing the power function using repeated squaring.