recursive algorithms for computing powers as another interesting example of the use of linear recursionwe consider the problem of raising number to an arbitrary nonnegative integern that iswe wish to compute the power functiondefined as power(xnxn (we use the name "powerfor this discussionto differentiate from the built-in function pow that provides such functionality we will consider two different recursive formulations for the problem that lead to algorithms with very different performance trivial recursive definition follows from the fact that xn xn- for if power(xnx power(xn otherwise this definition leads to recursive algorithm shown in code fragment def power(xn) """compute the value for integer "" if = return else return power(xn- code fragment computing the power function using trivial recursion recursive call to this version of power(xnruns in (ntime its recursion trace has structure very similar to that of the factorial function from figure with the parameter decreasing by one with each calland constant work performed at each of levels howeverthere is much faster way to compute the power function using an alternative definition that employs squaring technique let denote the floor of the division (expressed as / in pythonwe consider the expression xk when is evenn and therefore xk xn when is oddn - xn- and therefore xn xk just as and this analysis leads to the following recursive definitionif if is odd power(xnx power xn power xn if is even if we were to implement this recursion making two recursive calls to compute power( power( ) trace of the recursion would demonstrate (ncalls we can perform significantly fewer operations by computing power(xn as partial resultand then multiplying it by itself an implementation based on this recursive definition is given in code fragment