# Recursive lists in OOP
class Rlist(object):
    """A recursive list consisting of a first element and the rest.

    >>> s = Rlist(1, Rlist(2, Rlist(3)))
    >>> len(s)
    3
    >>> s[0]
    1
    >>> s[1]
    2
    >>> s[2]
    3
    """
    class EmptyList(object):
        def __len__(self):
            return 0
    empty = EmptyList()

    def __init__(self, first, rest=empty):
        self.first = first
        self.rest = rest

    def __repr__(self):
        f = repr(self.first)
        if self.rest is Rlist.empty:
            return 'Rlist({0})'.format(f)
        else:
            return 'Rlist({0}, {1})'.format(f, repr(self.rest))

    def __len__(self):
        return 1 + len(self.rest)

    def __getitem__(self, i):
        if i == 0:
            return self.first
        return self.rest[i - 1]

def extend_rlist(s1, s2):
    """Return a list containing the elements of s1 followed by those
    of s2.

    >>> s = Rlist(1, Rlist(2, Rlist(3)))
    >>> extend_rlist(s.rest, s)
    Rlist(2, Rlist(3, Rlist(1, Rlist(2, Rlist(3)))))
    """
    if s1 is Rlist.empty:
        return s2
    return Rlist(s1.first, extend_rlist(s1.rest, s2))

def map_rlist(s, fn):
    """Return an Rlist resulting from mapping fn over the elements of
    s.

    >>> s = Rlist(1, Rlist(2, Rlist(3)))
    >>> map_rlist(s, lambda x: x * x)
    Rlist(1, Rlist(4, Rlist(9)))
    """
    if s is Rlist.empty:
        return s
    return Rlist(fn(s.first), map_rlist(s.rest, fn))

def filter_rlist(s, fn):
    """Filter the elements of s by predicate fn.

    >>> s = Rlist(1, Rlist(2, Rlist(3)))
    >>> filter_rlist(s, lambda x: x % 2 == 1)
    Rlist(1, Rlist(3))
    """
    if s is Rlist.empty:
        return s
    rest = filter_rlist(s.rest, fn)
    if fn(s.first):
        return Rlist(s.first, rest)
    return rest

# Trees as nested tuples
t = ((1, 2), (3, 4), 5)

def count_leaves(tree):
    """Return the number of leaves in a tree.

    >>> count_leaves(t)
    5
    """
    if type(tree) != tuple:
        return 1
    return sum(map(count_leaves, tree))

# Tree class (binary trees with internal values)
class Tree(object):
    """A tree with internal values."""
    def __init__(self, entry, left=None, right=None):
        self.entry = entry
        self.left = left
        self.right = right

    def __repr__(self):
        args = repr(self.entry)
        if self.left or self.right:
            args += ', {0}, {1}'.format(repr(self.left), repr(self.right))
        return 'Tree({0})'.format(args)

# Fibonacci
def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fib(n - 2) + fib(n - 1)

def fib_iter(n):
    prev, curr = 1, 0
    for _ in range(n-1):
         prev, curr = curr, prev + curr
    return curr

# Counting factors
from math import sqrt

def count_factors(n):
    """Count the positive integers that evenly divide n.

    >>> count_factors(576)
    21
    """
    factors = 0
    for k in range(1, n + 1):
        if n % k == 0:
            print(k)
            factors += 1
    return factors

def count_factors_fast(n):
    """Count the positive integers that evenly divide n.

    >>> count_factors_fast(576)
    21
    """
    sqrt_n = sqrt(n)
    k, factors = 1, 0
    while k < sqrt_n:
        if n % k == 0:
            factors += 2
        k += 1
    if k * k == n:
        factors += 1
    return factors

# Exponentiation
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

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)