from operator import add, mul from math import sqrt, e # Recursion def factorial_iter(n): """Compute the factorial of a natural number. >>> factorial_iter(6) 720 """ if n == 0 or n == 1: return 1 total = 1 while n >= 1: total, n = total * n, n - 1 return total def factorial(n): """Compute the factorial of a natural number. >>> factorial(6) 720 """ if n == 0 or n == 1: return 1 return n * factorial(n - 1) # a, factorial = factorial 3 # a(4) # Reverse order recursion def factorial2(n): """Compute the factorial of a natural number. >>> factorial2(6) 720 """ return factorial_helper(n, 1) def factorial_helper(n, k): if k >= n: return k else: return k * factorial_helper(n, k + 1) # 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)