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

# Mutual recursion
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 factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

# Recursion to iteration
def summation_rec(n, term):
    """Sum the first n terms of the sequence specified by term.

    >>> summation_rec(5, lambda x: x*x)
    55
    """
    if n == 0:
        return 0
    return summation_rec(n - 1, term) + term(n)

def summation_iter(n, term):
    """Sum the first n terms of the sequence specified by term.

    >>> summation_iter(5, lambda x: x*x)
    55
    """
    total = 0
    while n > 0:
        total, n = total + term(n), n - 1
    return total

# Iteration to 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_rec(n):
    """Compute the nth Fibonacci number.

    >>> fib_rec(6)
    8
    """
    if n == 0:
        return 0
    return fib_rec_helper(n, 1, 0, 1)

def fib_rec_helper(n, fib_n, fib_n_minus_1, k):
    if k >= n:
        return fib_n
    return fib_rec_helper(n, fib_n + fib_n_minus_1, fib_n, k + 1)

# Currying
def curry2(f):
    """Returns a function g such that g(x)(y) == f(x, y).

    >>> from operator import add
    >>> add_three = curry2(add)(3)
    >>> add_three(4)
    7
    >>> from math import e
    >>> exp = curry2(pow)(e)
    >>> exp(2)
    7.3890560989306495
    """
    def outer(n):
        def inner(k):
            return f(n, k)
        return inner
    return outer

def uncurry2(f):
    """Returns a function f such that f(x, y) == g(x)(y).

    >>> from operator import add
    >>> uncurry2(curry2(add))(3, 4)
    7
    """
    return lambda x, y: f(x)(y)

# Rational numbers
def mul_rational(x, y):
    """Multiply two rationals together.

    >>> r = mul_rational(rational(3, 2), rational(3, 5))
    >>> numer(r) / denom(r)
    0.9
    """
    return rational(numer(x) * numer(y), denom(x) * denom(y))

def add_rational(x, y):
    """Add two rationals together.

    >>> r = add_rational(rational(3, 2), rational(3, 5))
    >>> numer(r) / denom(r)
    2.1
    """
    nx, dx = numer(x), denom(x)
    ny, dy = numer(y), denom(y)
    return rational(nx * dy + ny * dx, dx * dy)

def eq_rational(x, y):
    """Determine if two rationals are equal.

    >>> eq_rational(rational(1, 2), rational(2, 4))
    True
    >>> eq_rational(rational(1, 2), rational(3, 4))
    False
    """
    return numer(x) * denom(y) == numer(y) * denom(x)

# Representing rationals using tuples
def rational(n, d):
    """Construct a rational number x that represents n/d."""
    return (n, d)

from operator import getitem

def numer(x):
    """Return the numerator of rational number x."""
    return getitem(x, 0)

def denom(x):
    """Return the denominator of rational number x."""
    return getitem(x, 1)