An alternative strategy for the expo function uses the following recursive definition:
expo(number, exponent) = 1, when exponent = 0 = number * expo(number, exponent – 1), when exponent is odd = (expo(number, exponent // 2)) ** 2, when exponent is even
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
2 4
3 8
4 16
---------------------------------------------------------------------------------
def expo(base, exponent):
expo.calls += 1 # Used to track recursive call count
# Write you recursive expo function here
expo.calls = 0
def main():
"""Tests with powers of 2."""
for exponent in range (5):
print(exponent, expo(2, exponent))
if __name__ == "__main__":
main()