'''power.py

   Jed Yang, 2016-10-20

   For factorial, recursion doesn't help; for fibonacci, recursion was very
   bad.  Let's try to use what we learned to see why calculating power (that
   is, x ** n for some nonnegative integer n) might be better with recursion.

   You saw the first two implementations of power in class and tried to write
   the third on the worksheet.  The third is also found in Zelle 13.2.5.
'''

def power_iterative(x, n):
   '''Iteratively calculate x ** n = 1 * x * x * ... * x.'''
   product = 1
   for i in range(n):
      product = product * x
   return product


def power_recursive(x, n):
   '''Recursively calculate x ** n = x * (x ** (n-1))'''
#   print('Hi, power_recursive({0}, {1}) has been called.'.format(x, n))

   # This line should look familiar from fibonacci_recursive; we'll use it
   # later to track the number of calls to power_recursive, as you expected.
   power_recursive.totalCalls = power_recursive.totalCalls + 1

   if n == 0:
      return 1
   else:
      return x * power_recursive(x, n-1)

power_recursive.totalCalls = 0

def power_recursive_fast(x, n):
   '''Recursively calculate x ** n = (x ** n/2) * (x ** n/2) when n is even.'''
#   print('Hi, power_recursive_fast({0}, {1}) has been called.'.format(x, n))

   if n == 0:
      return 1
   else:
      factor = power_recursive_fast(x, n//2)
      if n % 2 == 0:                # n is even
         return factor * factor     # x**n = (x**(n/2)) * (x**(n/2))
      else:                         # n is odd, recall that n//2 = (n-1)/2
         return factor * factor * x # x**n = (x**((n-1)/2)) * (x**((n-1)2)) * x

def main():
   x = 2
   for i in range(10):
      print('{0} ** {1} = {2}.'.format(x, i, power_iterative(x, i)))
   for i in range(10):
      print('{0} ** {1} = {2}.'.format(x, i, power_recursive(x, i)))
   for i in range(10):
      print('{0} ** {1} = {2}.'.format(x, i, power_recursive_fast(x, i)))

# 1. Make sure you understand why power_recursive_fast gives the right answer.
#    Below, we will explore why it is fast.

#    Comment out the main().  Go below.
main()

def large(largeNumber):
   x = 2
   print('Recursive (fast):')
   print(power_recursive_fast(x, largeNumber))
   print('Recursive (slow):')
   print(power_recursive(x, largeNumber))
   print('Iterative:')
   print(power_iterative(x, largeNumber))

# 2. Uncomment the large(100) and see if the we can handle large numbers.

#large(100)

# 3. Again, try to find a breaking point, where power_recursive throws a
#    RuntimeError of reaching the recursion depth.  Can you find a value where
#    power_recursive doesn't work but power_recursive_fast still works?  [Hint:
#    comment out the power_recursive function call in order to continue trying
#    larger values.]  Can you go large enough where you can sense that
#    power_recursive_fast is noticeably faster than power_iterative?

#    Comment out the large(...) and move on.

# 4. Okay, so it seems like power_recursive_fast does not go as deep in the
#    recursion.  (Oops, I just gave away the answer for Question 3.  Hopefully
#    you already tried it.)  Let's track the actual number.
#
#    Uncomment the countCalls() below.
#
#    Can you see a pattern in the number of calls?

def countCalls():
   x = 2
   for i in range(10):
      # set totalCalls to 0 for each loop
      power_recursive.totalCalls = 0
      # print out the number of calls to power_recursive it took us to
      # calculate fib(i)
      print('{0} ** {1} = {2}; totalCalls = {3}'
         .format(x, i, power_recursive(x,i), power_recursive.totalCalls))

#countCalls()

# 5. Oops, that was boring.  Can you mimic the syntax of how we kept track of
#    the number of calls of fibonacci_recursive and power_recursive and use it
#    to track the number of calls to power_recursive_fast?
#
#    Can you see a pattern in the number of calls?