# Simple, but slow, Fibonacci numbers.
def fib(n):
    """The Nth Fibonacci number, N>=0."""
    assert n >= 0
    if n <= 1:
        return n
    else:
        return fib(n-2) + fib(n-1)

# Tail-recursive versions of fib:

def fib2(fk1, fk, k, n):
    """Assuming FK1 and FK2 are fib(K-1) and fib(K)
    in the Fibonacci sequence and that N>=K, return fib(N)."""
    if n == k:
        return fk
    else:
        return \{\underline{\vis{\Blue 2}{fib2(fk, fk1+fk, k+1, n)}}\}
def fib(n):
    if n <= 1:
       return n
    else:
       return fib2(0, 1, 1, n)


# Same, but with inner function

def fib(n):
    def fib2(fk1, fk, k):
        if n == k:
            return fk
        else:
            return fib2( fk, fk1+fk, k+1)

    if n <= 1:
        return n
    else:
        return fib2(0, 1, 1)

# What is printed? (I)
# (Changed from lecture to put definitions in a local frame instead of the
# global frame so that it can coexist with other quizzes.
# The result is the same.

def quiz1():
    def f():
        return 0

    def g():
        print(f())

    def h():
        def f():
            return 1
        g()

    h()

# What is printed? (II)

def quiz2():
    def f():
        return 0

    g = f

    def f():
        return 1

    print(g())


# What is printed? (III)

def quiz3():
    def f():
        return 0

    def g():
        print(f())

    def f():
        return 1

    g()

# Functions on functions

from operator import add, neg

def summation(N, f):
    k, sum = 1, 0
    while k <= N:
        sum, k = sum+f(k), k+1
    return sum

def sum_squares(N):
    def square(x):
        return x*x
    return summation(N, square)

# or

def sum_squares(N):
    return summation(N, lambda x: x*x)

def summations():
    print(summation(10, lambda x: x**3))      # Sum of cubes
    print(summation(10, lambda x: 1 / x))     # Harmonic series
    print(summation(10, lambda k: x**(k-1) / factorial(k-1)))
                                       # Approximate e**x
    
# Functions that return functions

def add_func(f, g):
    """Return function that returns F(x)+G(x) for argument x."""
    def adder(x):           #
        return f(x) + g(x)  # or return lambda x: f(x) + g(x)
    return adder            # 

h = add_func(add, neg)
print(h(-5))

# Generalizing still more:

def combine_funcs(op):
    def combined(f, g):
        def val(x):
            return op(f(x), g(x))
        return val
    return combined

# Now, can define instead

add_func = combine_funcs(add)

h = add_func(add, neg)
print(h(-5))