from operator import add, mul
from math import sqrt, e

# Tree recursion
def fib_iter(n):
    """Compute the nth Fibonacci number.

    >>> fib_iter(6)
    8
    """
    if n == 0:
        return 0
    fib_n, fib_n_minus_1 = 1, 0
    k = 1
    while k < n:
        fib_n, fib_n_minus_1 = fib_n_minus_1 + fib_n, fib_n
        k += 1
    return fib_n
    
def fib(n):
    """Compute the nth Fibonacci number.

    >>> fib(6)
    8
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

# Decorators
def trace1(fn):
    """Return a function equivalent to fn that also prints trace
    output.

    fn -- a function of one argument.
    """
    def traced(x):
        print('Calling:', fn, '(', x, ')')
        res = fn(x)
        print('Got', res, 'from', fn, '(', x, ')')
        return res
    return traced

@trace1
def cube(x):
    return pow(x, 3)

@trace1
def cube_this_and_next(x):
    return cube(x) + cube(x+1)

# Rebind the name fib to a traced version of fib
fib = trace1(fib)

# Pig Latin
def pig_latin(w):
    """Return the Pig Latin equivalent of a lowercase English word
    w."""
    if starts_with_a_vowel(w):
        return w + 'ay'
    return pig_latin(rest(w) + first(w))

def first(s):
    """Returns the first character of a string."""
    return s[0]

def rest(s):
    """Returns all but the first character of a string."""
    return s[1:]

def starts_with_a_vowel(w):
    """Return whether w begins with a vowel."""
    c = first(w)
    return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'

# Count change
def next_coin(d):
    if d == 50:
        return 25
    elif d == 25:
        return 10
    elif d == 10:
        return 5
    elif d == 5:
        return 1
    else:
        return 0

def count_change(a, d):
    """Count the number of ways to change amount a with coins no
    larger than d.

    >>> count_change(100, 50)
    292
    """
    if a == 0:
        return 1
    if a < 0 or d == 0:
        return 0
    return (count_change(a-d, d) + count_change(a, next_coin(d)))