# 3. Recursion¶

Don’t think too hard! That’s one of the central themes of this chapter. It’s not often that you tell computer programmers not to think too hard, but this is one time when it is appropriate. You need to read this chapter if you have not written recursive functions before. Most computer science students start by learning to program in a style called *imperative* programming. This simply means that you are likely used to thinking about creating variables, storing values, and updating those values as a program proceeds. In this chapter you are going to begin learning a different style of programming called *functional* programming. When you program in the functional style, you think much more about the definition of *what* you are programming than *how* you are going to program it. Some say that writing recursive functions is a *declarative* approach rather than an *imperative* approach. You’ll start to learn what that means for you very soon. When you start to get good at writing recursive functions you’ll be surprised how easy it can be!

## 3.1. Scope¶

You can `download the program` by clicking here.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | ```
import math
PI = math.pi
def area(radius):
global z
z = 6
theArea = PI * radius ** 2
return theArea
def main():
global z
historyOfPrompts = []
historyOfOutput = []
def getInput(prompt):
x = input(prompt)
historyOfPrompts.append(prompt)
return x
def showOutput(val):
historyOfOutput.append(val)
print(val)
rString = getInput("Please enter the radius of a circle: ")
r = float(rString)
val = area(r)
print(z)
showOutput("The area of the circle is " + str(val))
if __name__ == "__main__":
main()
``` |

## 3.2. Recursive Spiral¶

You can `download the program` by clicking here.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | ```
import turtle
def drawSpiral(t, length, color, colorBase):
#color is a 24 bit value that is changing a bit
#each time for a nice color effect
if length == 0:
return
# add 2^10 to the old color modulo 2^24
# the modulo 2^24 prevents the color from
# getting too big.
newcolor = (int(color[1:],16) + 2**10)%(2**24)
# find the color base integer value
base = int(colorBase[1:],16)
# now if the new color is less than the base
# add the base module 2^24.
if newcolor < base:
newcolor = (newcolor + base)%(2**24)
# let newcolor be the hex string after conversion.
newcolor = hex(newcolor)[2:]
# add a pound sign and zeroes to the front so it
# is 6 characters long plus the pound sign for a
# proper color string.
newcolor = "#"+("0"*(6-len(newcolor)))+newcolor
t.color(newcolor)
t.forward(length)
t.left(90)
drawSpiral(t, length-1, newcolor, colorBase)
def main():
t = turtle.Turtle()
screen = t.getscreen()
t.speed(100)
t.penup()
t.goto(-100,-100)
t.pendown()
drawSpiral(t, 200, "#000000", "#ff00ff")
screen.exitonclick()
if __name__ == "__main__":
main()
``` |

## 3.3. Sunflower Program¶

You can `download the program` by clicking here.

This program is not included in the text, but is a good program to look at when starting chapter 3. It illustrates the golden rule and the fibonacci sequence. Computing fibonacci numbers both recursively and iteratively can lead to a good discussion of computational complexity as well as recursion. You can write a program to time computing fibonacci numbers both recursively and iteratively. The recursive version will not handle numbers bigger than 20 or so. The iterative version can go very high. It is interesting to look at the graph of these two methods of computing fibonacci numbers as a contrast in what is efficient and what is not.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | ```
'''
Author: Kent D. Lee
Date: 9/26/2014
Copyright (c) 2014
Free for educational use. Others may use with permission.
Source:
I used http://fractalfoundation.org/OFC/OFC-11-3.html as a source for this
information.
Description:
This program draws sunflower seeds in the pattern of a funflower. The ration of
consecutive fibonacci numbers in the sequence approach the golden ratio as the
sequence grows. In the limit, the ratio of two consecutive fibonacci numbers is
the golden ratio.
In the sunflower fibonacci numbers can be observed by counting the number of seeds
in the spiral arms. Count the number of seeds in a left spiral arm and a right spiral
arm. You'll see that they are two fibonacci numbers.
You may have to make the radius size of the seeds constant to count the seeds. It won't
look as pretty, but will be easier to count. You may also need to increase the forward
to separate the seeds.
'''
import turtle
import math
class Circle:
def __init__(self,radius, width=1,color="white",outline="black"):
self.radius = radius
self.width = width
self.color = color
self.outline = outline
def draw(self,turtle):
centerX = turtle.xcor()
centerY = turtle.ycor()
turtle.penup()
turtle.goto(centerX+self.radius,centerY)
turtle.pendown()
turtle.width(self.width)
turtle.pencolor(self.outline)
turtle.fillcolor(self.color)
turtle.begin_fill()
for i in range(361):
newX = self.radius * math.cos((i/180.0) * math.pi) + centerX
newY = self.radius * math.sin((i/180.0) * math.pi) + centerY
turtle.goto(newX,newY)
turtle.end_fill()
turtle.penup()
turtle.goto(centerX, centerY)
turtle.pendown()
def main():
t = turtle.Turtle()
t.ht()
screen = t.getscreen()
screen.tracer(0)
for x in range(400):
c = Circle(x/16+4,width=2,color="yellow")
c.draw(t)
# This angle is chosen because it is approx.
# 360/1.61803399. The 1.61803399 is the approx.
# value of the golden angle
t.left(222.5)
t.penup()
t.forward(x*2 + 8)
screen.update()
screen.exitonclick()
if __name__ == "__main__":
main()
``` |