Recursion

A recursive function is one that calls itself. To use recursion, you must do four things.

1. Package the code as a function.


2. Do only part of the job, not all of it, in the function. For example, line 12 prints only one of the integers in the sequence of integers we want to print.


3. Call yourself to do the rest of the job. For example, line 13 in the function upTo10 calls upTo10 to print the rest of the sequence of integers. The +1 ensures that we don’t repeat the part of the job we just completed in line 12.


4. Write an if to make sure the function does not go into an infinite loop and call itself forever. For example, the if in line 11 prevents the function from doing anything else if the job has already been completed. In other words, if n > 10, the function does nothing.

recursion.py

1
2
3
4
5
6
7
8
9
10

Note that no variable changed its value as this program was running. In other words, there were no assignment statements. We never wrote = or +=.

There is no need to use recursion to print the numbers from 1 to 10: a for loop with a range would be simpler. Similarly, there is no need to use recursion for a problem shaped like a rectangle, where all the rows have the same length and all the columns have the same length. You would use recursion for an irregularly shaped problem, such as processing all the branches of an irregularly shaped tree. See Tree.

Things to try

1. Don’t hardwire the stopping point 10 into line 11. Let the user specify the stopping point as an argument when they call the function. And rename the function upToN. Change lines 9–16 to the following.

   def upToN(i, n):
       "Print the integers from i to n inclusive."
       if i <= n:
           print(i)
           upToN(i + 1, n)
   
   
   upToN(1, 12)
   

   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   



2. Can you count by twos? Or by tens?


3. Here are five ways to compute the factorial of an integer. Note that no variable changes its value in the recursive version.

   import math
   
   print(math.factorial(4))   #means 1 * 2 * 3 * 4
   

   24
   

   product = 1
   
   for i in range(1, 5):
       product *= i           #means product = product * i
   
   print(product)
   

   24
   

   import functools
   
   product = functools.reduce(lambda product, i: product * i, range(1, 5), 1)
   print(product)
   

   24
   

   The above two-argument function lambda product, i: product * i has already been written for us. Its name is operator.mul.

   import functools
   import operator
   
   product = functools.reduce(operator.mul, range(1, 5), 1)
   print(product)
   

   24
   

   def factorial(i):
       "Return the factorial of i."
       assert isinstance(i, int) and i >= 0
   
       if i <= 1:
           return i
       return factorial(i - 1) * i
   
   
   print(factorial(4))
   

   24
   

4. """
   Print the the prime numbers in the given range.
   """
   
   def sieve(seq):   #seq is a list or range
       "Return a list of the prime numbers in the given sequence."
       if not seq:   #if seq is empty
           return []
       #filteredList is seq with all the multiples of the first item removed.
       filteredList = list(filter(lambda n: n % seq[0], seq))
       return [seq[0]] + sieve(filteredList)
   
   print(sieve(range(2, 101)))
   

   [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
   

5. How low can you go?

   import sys
   
   print(sys.getrecursionlimit())
   
   def deliberateSuicide():
       deliberateSuicide()
   
   deliberateSuicide()
   sys.exit(0)   #We never arrive here.
   

   1000
   Traceback (most recent call last):
     File "/Users/myname/python/prog.py", line 9, in 
       deliberateSuicide()
     File "/Users/myname/python/prog.py", line 7, in deliberateSuicide
       deliberateSuicide()
     File "/Users/myname/python/prog.py", line 7, in deliberateSuicide
       deliberateSuicide()
     File "/Users/myname/python/prog.py", line 7, in deliberateSuicide
       deliberateSuicide()
     [Previous line repeated 991 more times]
   RecursionError: maximum recursion depth exceeded