# Recursive factorial def factorial(n): """Return the factorial of n. >>> factorial(0) 1 >>> factorial(1) 1 >>> factorial(5) 120 """ if n == 0: return 1 else: return n * factorial(n-1) # Sum digits def sum_digits(n): """Return the sum of the digits of positive integer n. >>> sum_digits(9) 9 >>> sum_digits(18117) 18 >>> sum_digits(9437184) 36 >>> sum_digits(11408855402054064613470328848384) 126 """ if n < 10: return n else: return sum_digits(n//10) + n%10 # Iterative factorial # Key idea in converting recursion to iteration: try to make the state # maintained in each iteration the same as the state maintained by each # recursive call def fact_iter(n): total, k = 1, 1 while k <= n: total, k = total * k, k + 1 return total # Converting back to recursion # More formulaic: whatever state is maintained in each iteration, pass # that in as arguments to the recursive function def fact2(n, total): if n == 0: return total else: return fact2(n-1, total*n) # Can be ugly or complicated, but often not too hard to clean up fact = lambda n: fact2(n, 1) # Minimum element in list def minimum(lst): """Return the minimum element in lst, a nonempty list of numbers. >>> minimum([0]) 0 >>> minimum([1, 2, 3]) 1 >>> minimum([1, -1, -4000, 2, 170]) -4000 """ if len(lst) == 1: return lst[0] else: return min(lst[0], minimum(lst[1:])) # Reverse string def reverse(word): """Given the string word, return word in reverse. >>> reverse('') '' >>> reverse('a') 'a' >>> reverse('Hello world!') '!dlrow olleH' """ if len(word) < 2: return word else: return reverse(word[1:]) + word[0]