Question

Programming Exercise 11.4 m | Instructions expo.py + An alternative strategy for the expo function uses the following recursive definition: 1 def expo (base, exponent): 2 expo.calls += 1 # Used to track recursive call count 3 # Write you recursive expo function here 4 5 expo.calls = 6 7 def main(): ***"Tests with powers of 2."" 9 for exponent in range (5): 10 print (exponent, expo(2, exponent)) 11 12 if name == "_main_": 13 main() 14 expo(number, exponent) = 1, when exponent = 0 = number * expo(number, exponent - 1), when exponent (expo(number, exponent // 2)) ** 2, when exponent 8 Define a recursive function expo that uses this strategy, and state its computational complexity using big o notation. Note: The program should output in the following format: 0 1 1 2 24 38 4 16 Grading When you have completed your program, click the Submit button to record your score.

Answer 1

CODE:

def expo(base, exponent):

expo.calls +=1 #Used to track recursive call counts

#recursive expo function

#if exponent == 0, then return 1 (as per the constraint)

if exponent == 0:

return 1

#if exponent == 1, then returing base as base^1 is base itself

if exponent == 1:

return base

# if exponent > 1, then using recursion function (as per the constraint)

# you can use the following two recursive methods to get the exponent

# if exponent != 1:

# return base * expo(base, exponent - 1)

if exponent != 1:

return expo(base, exponent // 2) ** 2

expo.calls = 0

def main():

for exponent in range(5):

print(exponent, expo(2,exponent))

print("Expo calls: ", expo.calls)

if __name__ == "__main__":

main()

CODE SCREENSHOTS:

1 def expo(base, exponent): expo.calls +=1 #Used to track recursive call counts 2. 3 4 5 #recursive expo function #if exponent 0, then return 1 (as per the constraint) if exponent return 1 6 7 8 9 10 11 12 #if exponent 1, then returing base as base^1 is base itself if exponent == 1: return base 13 # if exponent > 1, then using recursion function (as per the constraint) # you can use the following two recursive methods to get the exponent 14 15 16 17 # if exponent != 1: # return base * expo(base, exponent - 1) 18 if exponent != 1: return expo (base, exponent // 2) ** 2 expo.calls = 0 19 20 21 22 23 24 25 26 def main(): for exponent in range(5): print(exponent, expo(2, exponent)) print("Expo calls: ", expo.calls) 27 28 29 30 name == _main__": if main()

OUTPUT SCREENSHOT

0 1 Expo calls: 1 1 2 Expo calls: 2 24 Expo calls: 4 38 Expo calls: 7 4 16 Expo calls: 11

Hope this helps.