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)))