# Exploring Exponentiation

```"""Exponentiation functions

Explores section "1.2.4 Exponentiation" from Structure and Interpretation of
Computer Programs (SICP) by Abelson and Sussman.
"""

def slow_rec_exp(a, b):
"""Slow, recursive exponent function.

Calculates a**b recursively in both O(b) time and space.
"""
if b == 0:
return 1
else:
return a * slow_rec_exp(a, b - 1)

def slow_iter_exp(a, b):
"""Slow, iterative exponent function.

Calculates a**b iteratively in both O(b) time and space.
Note that the term 'iterative' here comes from the definition used in
SICP. Tail-recursion optimization is assumed.
"""
def helper(a, b, accum):
if b == 0:
return accum
else:
return helper(a, b - 1, a * accum)
return helper(a, b, 1)

def fast_rec_exp(a, b):
"""Fast, recursive exponent function.

Calculates a**b recursively in both O(log(b)) time and space.
This is a python translation of the fast-expt function from page 45 of
SICP.
"""
if b == 0:
return 1
elif b % 2 == 0:
n = fast_rec_exp(a, b / 2)
return n * n
else:
return a * fast_rec_exp(a, b - 1)

def fast_iter_exp(a, b):
"""Fast, iterative exponent function.

Calculates a**b iteratively in both O(log(b)) time and space.
This is a python solution to exercise 1.16 from SICP. As with slow_iter_exp
the tail-recursion optimization is assumed.
"""
def helper(a, b, accum):
if b == 0:
return accum
elif b % 2 == 0:
a = a * a
b = b / 2
else:
accum = accum * a
b = b - 1
return helper(a, b, accum)
return helper(a, b, 1)```