# 16. Recursion ## 16.1. What Is Recursion? **Recursion** is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program. ## 16.2. Calculating the Sum of a List of Numbers We will begin our investigation with a simple problem that you already know how to solve without using recursion. Suppose that you want to calculate the sum of a list of numbers such as: \([1, 3, 5, 7, 9]\). An iterative function that computes the sum is shown below. The function uses an accumulator variable (`theSum`) to compute a running total of all the numbers in the list by starting with \(0\) and adding each number in the list. ```python def listsum(numList): theSum = 0 for i in numList: theSum = theSum + i return theSum print(listsum([1,3,5,7,9])) ``` Pretend for a minute that you do not have `while` loops or `for` loops. How would you compute the sum of a list of numbers? If you were a mathematician you might start by recalling that addition is a function that is defined for two parameters, a pair of numbers. To redefine the problem from adding a list to adding pairs of numbers, we could rewrite the list as a fully parenthesized expression. Such an expression looks like this: \[((((1 + 3) + 5) + 7) + 9)\] We can also parenthesize the expression the other way around, \[(1 + (3 + (5 + (7 + 9))))\] Notice that the innermost set of parentheses, \((7 + 9)\), is a problem that we can solve without a loop or any special constructs. In fact, we can use the following sequence of simplifications to compute a final sum. \[\begin{split}total = \ (1 + (3 + (5 + (7 + 9)))) \\ total = \ (1 + (3 + (5 + 16))) \\ total = \ (1 + (3 + 21)) \\ total = \ (1 + 24) \\ total = \ 25\end{split}\] How can we take this idea and turn it into a Python program? First, let’s restate the sum problem in terms of Python lists. We might say the the sum of the list `numList` is the sum of the first element of the list (`numList[0]`), and the sum of the numbers in the rest of the list (`numList[1:]`). To state it in a functional form: \[ listSum(numList) = first(numList) + listSum(rest(numList)) \label{eqn:listsum}\] In this equation \(first(numList)\) returns the first element of the list and \(rest(numList)\) returns a list of everything but the first element. This is easily expressed in Python. ```python def listsum(numList): if len(numList) == 1: return numList[0] else: return numList[0] + listsum(numList[1:]) print(listsum([1,3,5,7,9])) ``` There are a few key ideas in this listing to look at. First, on line 2 we are checking to see if the list is one element long. This check is crucial and is our escape clause from the function. The sum of a list of length 1 is trivial; it is just the number in the list. Second, on line 5 our function calls itself! This is the reason that we call the `listsum` algorithm recursive. A recursive function is a function that calls itself. [Figure 1](#fig-recsumin) shows the series of **recursive calls** that are needed to sum the list \([1, 3, 5, 7, 9]\). You should think of this series of calls as a series of simplifications. Each time we make a recursive call we are solving a smaller problem, until we reach the point where the problem cannot get any smaller.  Figure 1: Series of Recursive Calls Adding a List of Numbers When we reach the point where the problem is as simple as it can get, we begin to piece together the solutions of each of the small problems until the initial problem is solved. [Figure 2](#fig-recsumout) shows the additions that are performed as `listsum` works its way backward through the series of calls. When `listsum` returns from the topmost problem, we have the solution to the whole problem.  Figure2: Series of Recursive Returns from Adding a List of Numbers ## 16.3. The Three Laws of Recursion Like the robots of Asimov, all recursive algorithms must obey three important laws: 1. A recursive algorithm must have a **base case**. 2. A recursive algorithm must change its state and move toward the base case. 3. A recursive algorithm must call itself, recursively. Let’s look at each one of these laws in more detail and see how it was used in the `listsum` algorithm. First, a base case is the condition that allows the algorithm to stop recursing. A base case is typically a problem that is small enough to solve directly. In the `listsum` algorithm the base case is a list of length 1. To obey the second law, we must arrange for a change of state that moves the algorithm toward the base case. A change of state means that some data that the algorithm is using is modified. Usually the data that represents our problem gets smaller in some way. In the `listsum` algorithm our primary data structure is a list, so we must focus our state-changing efforts on the list. Since the base case is a list of length 1, a natural progression toward the base case is to shorten the list. This is exactly what happens on line 5 of [ActiveCode 2](CalculatingtheSumofaListofNumbers.html#lst-recsum) when we call `listsum` with a shorter list. The final law is that the algorithm must call itself. This is the very definition of recursion. Recursion is a confusing concept to many beginning programmers. As a novice programmer, you have learned that functions are good because you can take a large problem and break it up into smaller problems. The smaller problems can be solved by writing a function to solve each problem. When we talk about recursion it may seem that we are talking ourselves in circles. We have a problem to solve with a function, but that function solves the problem by calling itself! But the logic is not circular at all; the logic of recursion is an elegant expression of solving a problem by breaking it down into a smaller and easier problems. In the remainder of this chapter we will look at more examples of recursion. In each case we will focus on designing a solution to a problem by using the three laws of recursion. Self Check How many recursive calls are made when computing the sum of the list [2,4,6,8,10]? * 6 * There are only five numbers on the list, the number of recursive calls will not be greater than the size of the list. * 5 * The initial call to listsum is not a recursive call. * 4 * the first recursive call passes the list [4,6,8,10], the second [6,8,10] and so on until [10]. * 3 * This would not be enough calls to cover all the numbers on the list Suppose you are going to write a recusive function to calculate the factorial of a number. fact(n) returns n \* n-1 \* n-2 \* … \* 1, and the factorial of zero is definded to be 1. What would be the most appropriate base case? * n == 0 * Although this would work there are better and slightly more efficient choices. since fact(1) and fact(0) are the same. * n == 1 * A good choice, but what happens if you call fact(0)? * n >= 0 * This basecase would be true for all numbers greater than zero so fact of any positive number would be 1. * n <= 1 * Good, this is the most efficient, and even keeps your program from crashing if you try to compute the factorial of a negative number. ## 16.4. Converting an Integer to a String in Any Base Suppose you want to convert an integer to a string in some base between binary and hexadecimal. For example, convert the integer 10 to its string representation in decimal as `"10"`, or to its string representation in binary as `"1010"`. While there are many approaches one can take to solve this problem, the recursive formulation of the problem is very elegant. Let’s look at a concrete example using base 10 and the number 769. Suppose we have a sequence of characters corresponding to the first 10 digits, like `convString = "0123456789"`. It is easy to convert a number less than 10 to its string equivalent by looking it up in the sequence. For example, if the number is 9, then the string is `convString[9]` or `"9"`. If we can arrange to break up the number 769 into three single-digit numbers, 7, 6, and 9, then converting it to a string is simple. A number less than 10 sounds like a good base case. Knowing what our base is suggests that the overall algorithm will involve three components: 1. Reduce the original number to a series of single-digit numbers. 2. Convert the single digit-number to a string using a lookup. 3. Concatenate the single-digit strings together to form the final result. The next step is to figure out how to change state and make progress toward the base case. Since we are working with an integer, let’s consider what mathematical operations might reduce a number. The most likely candidates are division and subtraction. While subtraction might work, it is unclear what we should subtract from what. Integer division with remainders gives us a clear direction. Let’s look at what happens if we divide a number by the base we are trying to convert to. Using integer division to divide 769 by 10, we get 76 with a remainder of 9. This gives us two good results. First, the remainder is a number less than our base that can be converted to a string immediately by lookup. Second, we get a number that is smaller than our original and moves us toward the base case of having a single number less than our base. Now our job is to convert 76 to its string representation. Again we will use integer division plus remainder to get results of 7 and 6 respectively. Finally, we have reduced the problem to converting 7, which we can do easily since it satisfies the base case condition of \(n < base\), where \(base = 10\). The series of operations we have just performed is illustrated in [Figure 3](#fig-tostr). Notice that the numbers we want to remember are in the remainder boxes along the right side of the diagram.  Figure 3: Converting an Integer to a String in Base 10 The activecode below shows the Python code that implements the algorithm outlined above for any base between 2 and 16. ```python def toStr(n,base): convertString = "0123456789ABCDEF" if n < base: return convertString[n] else: return toStr(n//base,base) + convertString[n%base] print(toStr(1453,16)) ``` Notice that in line 3 we check for the base case where `n` is less than the base we are converting to. When we detect the base case, we stop recursing and simply return the string from the `convertString` sequence. In line 6 we satisfy both the second and third laws–by making the recursive call and by reducing the problem size–using division. Let’s trace the algorithm again; this time we will convert the number 10 to its base 2 string representation (`"1010"`).  Figure 4: Converting the Number 10 to its Base 2 String Representation [Figure 4](#fig-tostr2) shows that we get the results we are looking for, but it looks like the digits are in the wrong order. The algorithm works correctly because we make the recursive call first on line 6, then we add the string representation of the remainder. If we reversed returning the `convertString` lookup and returning the `toStr` call, the resulting string would be backward! But by delaying the concatenation operation until after the recursive call has returned, we get the result in the proper order. Self Check Write a function that takes a string as a parameter and returns a new string that is the reverse of the old string. ```python from test import testEqual def reverse(s): return s testEqual(reverse("hello"),"olleh") testEqual(reverse("l"),"l") testEqual(reverse("follow"),"wollof") testEqual(reverse(""),"") ``` Write a function that takes a string as a parameter and returns True if the string is a palindrome, False otherwise. Remember that a string is a palindrome if it is spelled the same both forward and backward. for example: radar is a palindrome. for bonus points palindromes can also be phrases, but you need to remove the spaces and punctuation before checking. for example: madam i’m adam is a palindrome. Other fun palindromes include: * kayak * aibohphobia * Live not on evil * Reviled did I live, said I, as evil I did deliver * Go hang a salami; I’m a lasagna hog. * Able was I ere I saw Elba * Kanakanak – a town in Alaska * Wassamassaw – a town in South Dakota ```python from test import testEqual def removeWhite(s): return s def isPal(s): return False testEqual(isPal(removeWhite("x")),True) testEqual(isPal(removeWhite("radar")),True) testEqual(isPal(removeWhite("hello")),False) testEqual(isPal(removeWhite("")),True) testEqual(isPal(removeWhite("hannah")),True) testEqual(isPal(removeWhite("madam i'm adam")),True) ``` ## 16.5. Visualizing Recursion Some problems are easy to solve using recursion; however, it can still be difficult to find a mental model or a way of visualizing what is happening in a recursive function. This can make recursion difficult for people to grasp. In this section we will look at using recursion to draw some interesting pictures. As you watch these pictures take shape you will get some new insight into the recursive process that may be helpful in cementing your understanding of recursion. For our next program we are going to draw a fractal tree. Fractals come from a branch of mathematics, and have much in common with recursion. The definition of a fractal is that when you look at it the fractal has the same basic shape no matter how much you magnify it. Some examples from nature are the coastlines of continents, snowflakes, mountains, and even trees or shrubs. The fractal nature of many of these natural phenomenon makes it possible for programmers to generate very realistic looking scenery for computer generated movies. In our next example we will generate a fractal tree. To understand how this is going to work it is helpful to think of how we might describe a tree using a fractal vocabulary. Remember that we said above that a fractal is something that looks the same at all different levels of magnification. If we translate this to trees and shrubs we might say that even a small twig has the same shape and characteristics as a whole tree. Using this idea we could say that a *tree* is a trunk, with a smaller *tree* going off to the right and another smaller *tree* going off to the left. If you think of this definition recursively it means that we will apply the recursive definition of a tree to both of the smaller left and right trees. Let’s translate this idea to some Python code. [Listing 1](#lst-fractree) shows how we can use our turtle to generate a fractal tree. Let’s look at the code a bit more closely. You will see that on lines 5 and 7 we are making a recursive call. On line 5 we make the recursive call right after the turtle turns to the right by 20 degrees; this is the right tree mentioned above. Then in line 7 the turtle makes another recursive call, but this time after turning left by 40 degrees. The reason the turtle must turn left by 40 degrees is that it needs to undo the original 20 degree turn to the right and then do an additional 20 degree turn to the left in order to draw the left tree. Also notice that each time we make a recursive call to `tree` we subtract some amount from the `branchLen` parameter; this is to make sure that the recursive trees get smaller and smaller. You should also recognize the initial `if` statement on line 2 as a check for the base case of `branchLen` getting too small. **Listing 1** ```python 1def tree(branchLen,t): 2 if branchLen > 5: 3 t.forward(branchLen) 4 t.right(20) 5 tree(branchLen-15,t) 6 t.left(40) 7 tree(branchLen-10,t) 8 t.right(20) 9 t.backward(branchLen) ``` The complete program for this tree example is shown below. Before you run the code think about how you expect to see the tree take shape. Look at the recursive calls and think about how this tree will unfold. Will it be drawn symmetrically with the right and left halves of the tree taking shape simultaneously? Will it be drawn right side first then left side? ```python import turtle def tree(branchLen,t): if branchLen > 5: t.forward(branchLen) t.right(20) tree(branchLen-15,t) t.left(40) tree(branchLen-15,t) t.right(20) t.backward(branchLen) def main(): t = turtle.Turtle() myWin = turtle.Screen() t.left(90) t.up() t.backward(100) t.down() t.color("green") tree(75,t) myWin.exitonclick() main() ``` Notice how each branch point on the tree corresponds to a recursive call, and notice how the tree is drawn to the right all the way down to its shortest twig. You can see this in [Figure 1](#fig-tree1). Now, notice how the program works its way back up the trunk until the entire right side of the tree is drawn. You can see the right half of the tree in [Figure 2](#fig-tree2). Then the left side of the tree is drawn, but not by going as far out to the left as possible. Rather, once again the entire right side of the left tree is drawn until we finally make our way out to the smallest twig on the left.  Figure 1: The Beginning of a Fractal Tree  Figure 2: The First Half of the Tree This simple tree program is just a starting point for you, and you will notice that the tree does not look particularly realistic because nature is just not as symmetric as a computer program. Here are a few ideas for how to explore some interesting options to make your tree look more realistic. Self Check Modify the recursive tree program using one or all of the following ideas: * Modify the thickness of the branches so that as the `branchLen` gets smaller, the line gets thinner. * Modify the color of the branches so that as the `branchLen` gets very short it is colored like a leaf. * Modify the angle used in turning the turtle so that at each branch point the angle is selected at random in some range. For example choose the angle between 15 and 45 degrees. Play around to see what looks good. * Modify the `branchLen` recursively so that instead of always subtracting the same amount you subtract a random amount in some range. ## 16.6. Sierpinski Triangle Another fractal that exhibits the property of self-similarity is the Sierpinski triangle. An example is shown in [Figure 3](#fig-sierpinski). The Sierpinski triangle illustrates a three-way recursive algorithm. The procedure for drawing a Sierpinski triangle by hand is simple. Start with a single large triangle. Divide this large triangle into four new triangles by connecting the midpoint of each side. Ignoring the middle triangle that you just created, apply the same procedure to each of the three corner triangles. Each time you create a new set of triangles, you recursively apply this procedure to the three smaller corner triangles. You can continue to apply this procedure indefinitely if you have a sharp enough pencil. Before you continue reading, you may want to try drawing the Sierpinski triangle yourself, using the method described.  Figure 3: The Sierpinski Triangle Since we can continue to apply the algorithm indefinitely, what is the base case? We will see that the base case is set arbitrarily as the number of times we want to divide the triangle into pieces. Sometimes we call this number the “degree” of the fractal. Each time we make a recursive call, we subtract 1 from the degree until we reach 0. When we reach a degree of 0, we stop making recursive calls. The code that generated this Sierpinski Triangle is shown below. ```python import turtle def drawTriangle(points,color,myTurtle): myTurtle.fillcolor(color) myTurtle.up() myTurtle.goto(points[0][0],points[0][1]) myTurtle.down() myTurtle.begin_fill() myTurtle.goto(points[1][0],points[1][1]) myTurtle.goto(points[2][0],points[2][1]) myTurtle.goto(points[0][0],points[0][1]) myTurtle.end_fill() def getMid(p1,p2): return ( (p1[0]+p2[0]) / 2, (p1[1] + p2[1]) / 2) def sierpinski(points,degree,myTurtle): colormap = ['blue','red','green','white','yellow', 'violet','orange'] drawTriangle(points,colormap[degree],myTurtle) if degree > 0: sierpinski([points[0], getMid(points[0], points[1]), getMid(points[0], points[2])], degree-1, myTurtle) sierpinski([points[1], getMid(points[0], points[1]), getMid(points[1], points[2])], degree-1, myTurtle) sierpinski([points[2], getMid(points[2], points[1]), getMid(points[0], points[2])], degree-1, myTurtle) def main(): myTurtle = turtle.Turtle() myWin = turtle.Screen() myPoints = [[-100,-50],[0,100],[100,-50]] sierpinski(myPoints,3,myTurtle) myWin.exitonclick() main() ``` This program follows the ideas outlined above. The first thing `sierpinski` does is draw the outer triangle. Next, there are three recursive calls, one for each of the new corner triangles we get when we connect the midpoints. Look at the code and think about the order in which the triangles will be drawn. While the exact order of the corners depends upon how the initial set is specified, let’s assume that the corners are ordered lower left, top, lower right. Because of the way the `sierpinski` function calls itself, `sierpinski` works its way to the smallest allowed triangle in the lower-left corner, and then begins to fill out the rest of the triangles working back. Then it fills in the triangles in the top corner by working toward the smallest, topmost triangle. Finally, it fills in the lower-right corner, working its way toward the smallest triangle in the lower right. Sometimes it is helpful to think of a recursive algorithm in terms of a diagram of function calls. [Figure 4](#fig-stcalltree) shows that the recursive calls are always made going to the left. The active functions are outlined in black, and the inactive function calls are in gray. The farther you go toward the bottom of [Figure 4](#fig-stcalltree), the smaller the triangles. The function finishes drawing one level at a time; once it is finished with the bottom left it moves to the bottom middle, and so on.  Figure 4: Building a Sierpinski Triangle The `sierpinski` function relies heavily on the `getMid` function. `getMid` takes as arguments two endpoints and returns the point halfway between them. In addition, this program has a function that draws a filled triangle using the `begin_fill` and `end_fill` turtle methods. ## 16.7. Glossary base case : A branch of the conditional statement in a recursive function that does not give rise to further recursive calls. data structure : An organization of data for the purpose of making it easier to use. immutable data type : A data type which cannot be modified. Assignments to elements or slices of immutable types cause a runtime error. infinite recursion : A function that calls itself recursively without ever reaching the base case. Eventually, an infinite recursion causes a runtime error. mutable data type : A data type which can be modified. All mutable types are compound types. Lists and dictionaries (see next chapter) are mutable data types; strings and tuples are not. recursion : The process of calling the function that is already executing. recursive call : The statement that calls an already executing function. Recursion can even be indirect — function f can call g which calls h, and h could make a call back to f. recursive definition : A definition which defines something in terms of itself. To be useful it must include *base cases* which are not recursive. In this way it differs from a *circular definition*. Recursive definitions often provide an elegant way to express complex data structures. tuple : A data type that contains a sequence of elements of any type, like a list, but is immutable. Tuples can be used wherever an immutable type is required, such as a key in a dictionary (see next chapter). tuple assignment : An assignment to all of the elements in a tuple using a single assignment statement. Tuple assignment occurs in parallel rather than in sequence, making it useful for swapping values. ## 16.8. Programming Exercises 1. Write a recursive function to compute the factorial of a number. ```python def computeFactorial(number): #your code here ===== from unittest.gui import TestCaseGui class myTests(TestCaseGui): def testOne(self): self.assertEqual(computeFactorial(0),1,"Tested computeFactorial on input 0") self.assertEqual(computeFactorial(1),1,"Tested computeFactorail on input 1") self.assertEqual(computeFactorial(2),2,"Tested computeFactorial on input 2") self.assertEqual(computeFactorial(3),6,"Tested computeFactorial on input 3") self.assertEqual(computeFactorial(4),24,"Tested computeFactorial on input 4") self.assertEqual(computeFactorial(8),40320,"Tested computeFactorial on input 8") self.assertEqual(computeFactorial(-5),None,"Tested computeFactorial on a negative number - make sure to handle this case") myTests().main() ``` 2. Write a recursive function to reverse a list. ```python def reverseList(lst): #your code here ===== from unittest.gui import TestCaseGui class myTests(TestCaseGui): def testOne(self): self.assertEqual(reverseList([1,2,3,4,5]), [5,4,3,2,1], "Your function failed with input [1,2,3,4,5]") self.assertEqual(reverseList(['Hello','World','!']), ['!','World','Hello'], "Your function failed with input ['Hello,'World','!']") self.assertEqual(reverseList(['Python',100,'35','Computer Science']), ['Computer Science', '35', 100, 'Python'], "Your function failed with input ['Python,100,'35','Computer Science']") myTests().main() ``` 3. Modify the recursive tree program using one or all of the following ideas: * Modify the thickness of the branches so that as the `branchLen` gets smaller, the line gets thinner. * Modify the color of the branches so that as the `branchLen` gets very short it is colored like a leaf. * Modify the angle used in turning the turtle so that at each branch point the angle is selected at random in some range. For example choose the angle between 15 and 45 degrees. Play around to see what looks good. * Modify the `branchLen` recursively so that instead of always subtracting the same amount you subtract a random amount in some range. If you implement all of the above ideas you will have a very realistic looking tree. 4. Find or invent an algorithm for drawing a fractal mountain. Hint: One approach to this uses triangles again. 5. Write a recursive function to compute the Fibonacci sequence. How does the performance of the recursive function compare to that of an iterative version? 6. Implement a solution to the Tower of Hanoi using three stacks to keep track of the disks. 7. Using the turtle graphics module, write a recursive program to display a Hilbert curve. 8. Using the turtle graphics module, write a recursive program to display a Koch snowflake. 9. Write a program to solve the following problem: You have two jugs: a 4-gallon jug and a 3-gallon jug. Neither of the jugs have markings on them. There is a pump that can be used to fill the jugs with water. How can you get exactly two gallons of water in the 4-gallon jug? 10. Generalize the problem above so that the parameters to your solution include the sizes of each jug and the final amount of water to be left in the larger jug. 11. Write a program that solves the following problem: Three missionaries and three cannibals come to a river and find a boat that holds two people. Everyone must get across the river to continue on the journey. However, if the cannibals ever outnumber the missionaries on either bank, the missionaries will be eaten. Find a series of crossings that will get everyone safely to the other side of the river. 12. Modify the Tower of Hanoi program using turtle graphics to animate the movement of the disks. Hint: You can make multiple turtles and have them shaped like rectangles. 13. Pascal’s triangle is a number triangle with numbers arranged in staggered rows such that \[a\_{nr} = {n! \over{r! (n-r)!}}\] This equation is the equation for a binomial coefficient. You can build Pascal’s triangle by adding the two numbers that are diagonally above a number in the triangle. An example of Pascal’s triangle is shown below. ```python 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ``` Write a program that prints out Pascal’s triangle. Your program should accept a parameter that tells how many rows of the triangle to print. ## 16.9. Exercises Adding this blank exercises page to hold instructor written questions.