Recursion can be applied to lots of different problems including sorting, searching, drawing pictures, etc. The program given in Sect. 3.6.1 draws a spiral on the screen as shown in Fig. 3.8.

3.6.1 Recursive Spiral

1 import turtle

2

3 def drawSpiral(t, length, color, colorBase):

4 #color is a 24 bit value that is changing a bit

5 #each time for a nice color effect

6 if length == 0:

7 return

8

9 # add 2ˆ10 to the old color modulo 2ˆ24

10 # the modulo 2ˆ24 prevents the color from

11 # getting too big.

12 newcolor = (int(color[1:],16) + 2**10)%(2**24)

13

14 # find the color base integer value

15 base = int(colorBase[1:],16)

16

17 # now if the new color is less than the base

18 # add the base modulo 2ˆ24.

19 if newcolor < base:

20 newcolor = (newcolor + base)%(2**24)

21

22 # let newcolor be the hex string after conversion.

23 newcolor = hex(newcolor)[2:]

24

25 # add a pound sign and zeroes to the front so it

26 # is 6 characters long plus the pound sign for a

In this program the drawSpiral function is recursive. It has a base case that is written first: when the length of the side is zero it exits. It calls itself on something smaller: the new length passed to it is the old length minus one. The newcolor formula is perhaps the most complex part of the code. There is some slicing going on there to convert the color string from a hexadecimal string to an integer so 1024 can be added, modulo 2 to the 24th. Then it must be converted back to a hexadecimal color string with the “#ffffff” format. The program draws a spiral like the one pictured in Fig. 3.8. Notice that this recursive function does not return anything. Most recursive functions do return a value. This one does not because the purpose of the function is to draw a spiral. It has a side-effect instead of returning a value.

3.7 Recursion on Lists and Strings

Recursive functions can be written for many different purposes. Many problems can be solved by solving a simpler problem and then applying that simpler solution recursively. For instance, consider trying to write a function that returns the reverse of a list. If we wrote this non-recursively, we might write it as follows.

3.7.1 List Recursion

1 def revList(lst):

2 accumulator = []

3

4 for x in lst:

5 accumulator = [x] + accumulator

6

7 return accumulator

8

9 def main():

10 print(revList([1,2,3,4]))

11

12 if name == " main ":

13 main()

When run, this program prints [4, 3, 2, 1] to the screen. The code in Sect. 3.7.1 uses the accumulator pattern to solve the problem of reversing a list. This is a pattern you have probably used before if you first learned to program imperatively. If we think about the problem recursively, we would first consider how to reverse a very simple list, say the empty list. The reverse of the empty list is just the empty list.

Once we have solved the problem for a very simple list, we can assume that if we call a recursive reverse function on something smaller (i.e. a shorter list), it will work. So, then to complete a recursive solution, we have only to piece our solution together. A recursive solution to reversing a list is found in Sect. 3.7.2.

Found a mistake? Please highlight the word and press Shift + Enter