# 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 # Count up to a number with print expressions # With recursion by enumeration first since it's a bit easier to demonstrate def count_up(n): """Recursively print up to n. >>> count_up(5) 1 2 3 4 5 """ if n == 1: print(1) elif n == 2: print(1) print(2) elif n == 3: print(1) print(2) print(3) elif n == 4: count_up(3) print(4) else: count_up(n - 1) print(n) # Now, a cleaned-up version def count_up(n): """Recursively print up to n. >>> count_up(5) 1 2 3 4 5 """ if n >= 1: count_up(n - 1) print(n) # 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)