of course ( putting the calculation together we start with ( and ( and ( we have calculated the value of using just three multiplications the basic insight is to use the relationship an an/ (an/ in the example gavethe exponents were all even in order to turn this idea into general algorithmwe also have to handle odd values of this can be done with one more multiplication for example ( )( here is the general relationshipn an// (an// if is even an// (an// )(aif is odd in this formula am exploiting integer divisionif is then // is we can use this relationship as the basis of recursive functionwe just need to find suitable base case notice that computing the nth power requires computing two smaller powers ( // if we keep using smaller and smaller values of nit will eventually get to ( // in integer divisionas you know from math classa for any value of (except there' our base case if you've followed all the maththe implementation of the function is straightforward def recpower(an)raises to the int power if = return elsefactor recpower(an// if % = is even return factor factor elsen is odd return factor factor one thing to notice is that used an intermediate variable factor so that an// only needs to be calculated once this makes the function more efficient examplebinary search now that you know how to implement recursive functionswe are ready to go back and look again at binary search recursively rememberthe basic idea was to look at the middle value and then recursively search either the lower half or the upper half of the array the base cases for the recursion are the conditions when we can stopnamelywhen the target value is found or we run out of places to look the recursive calls will cut the size of the problem in half each time in order to do thiswe need to specify the range of locations in the list that are still "in playfor each recursive call we can do this by passing the values of low and high as parameters along with the list each invocation will search the list between the low and high indexes here is direct implementation of the recursive algorithm using these ideasdef recbinsearch(xnumslowhigh)