Lecture Notes on 3 and 5 April 2017 Recursive Definition of Factorial n! = 1 * 2 * 3 ... * (n - 1) * n n! = n * (n - 1)! 0! = 1 Recursive Function for Factorial def fact (n): if (n == 0): return 1 else: return n * fact (n - 1) Computation of 4! goes all the way to 0 fact (4) 4 * fact (3) = 4 * 6 = 24 3 * fact (2) = 3 * 2 = 6 2 * fact (1) = 2 * 1 = 2 1 * fact (0) = 1 * 1 = 1 fact(0) return 1 def main(): var = fact (4) print (var) main() Fibonacci Series n 0 1 2 3 4 5 6 7 8 9 10 fib(n) 0 1 1 2 3 5 8 13 21 34 55 Recursive Function to Compute Fibonacci def fib (n): if (n == 0) or (n == 1): return n else: return fib (n - 1) + fib (n - 2) fib (6) = fib(5) + fib(4) = 5 + fib (4) fib (5) = fib (4) + fib(3) = 3 + 2 = 5 fib(4) = fib (3) + fib (2) = 2 + 1 = 3 fib(3) = fib (2) + fib (1) = 1 + 1 = 2 fib (2) = fib (1) + fib (0) = 1 + 0 = 1 fib (1) = 1 fib (0) = 0 Iterative Version of summing n numbers def sum_iter (n): sum_n = 0 for i in range (1, n + 1): sum_n += i return sum_n Recursive Version of summing n numbers def sum_rec (n): if (n == 1): return n else: return n + sum_rec (n - 1) Iterative version of summing the digits of a number def sum_digits (n): sum_d = 0 while (n > 0): sum_d += (n % 10) n = n // 10 return sum_d Recursive version of summing the digits of a number def sum_digits_rec (n): if (n == 0): return n else: return (n % 10) + sum_digits_rec (n // 10) Euclid's Greatest Common Divisor Algorithm def gcd (p, q): if (p == q): return p else: if (p > q): return gcd (p - q, q) else: return gcd (p, q - p) Recurrence Relation f(n) = 0 when n = 0 f(n) = 1 + 2 * f(n - 1) when n > 0 def func (n): if (n == 0): return n else: return 1 + 2 * func (n - 1) def func_iter (n): sum_n = 0 for i in range (n): sum_n = 1 + 2 * sum_n return sum_n n f(n) 0 0 1 1 2 3 3 7 4 15 5 31 6 63 7 127