"""Lecture 21 examples: Orders of growth"""

from ucb import trace, main, interact

@trace
def exp(b, n):
    """Return b to the n.

    >>> exp(2, 10)
    1024
    """
    if n == 0:
        return 1
    return b * exp(b, n-1)

def square(x):
    return x*x

@trace
def fast_exp(b, n):
    """Return b to the n.

    >>> fast_exp(2, 10)
    1024
    """
    if n == 0:
        return 1
    if n % 2 == 0:
        return square(fast_exp(b, n//2))
    else:
        return b * fast_exp(b, n-1)

@main
def run():
    interact()