A Very Brief Look at Recursion (We'll See More Later)

Recursion

Recursion is a process of repeating something in a self similar way. When we define a recursive function, we define a function in terms of itself. That is, it can call itself to define itself!

A couple of examples where we'll use recursion are:

• an approach to generating a mathematical sequence or computing a mathematical operation
• generating a fractal

Fractals

You know… fractals!

• Pizza Fractal
• The Largest Island in a Lake…

Back to Recursion

So… to create a recursive function definition:

• you'll need to create a function that calls itself
• a way for the function to stop calling itself (sometimes called a base case)
• otherwise… what do you think will happen here?

def is_this_forever():
	print("yes")
	is_this_forever()

is_this_forever()

Factorial Revisited

If we look at factorial again….

• 5! = 5 * 4 * 3 * 2 * 1
• can be rewritten as: 5 * 4!
• we can define factorial in terms of itself!
• (note that 0! is 1)

Factorial Using Recursion

Let's try to reimplement factorial using recursion rather than a loop. →

• we'll need to call the function within its definition
• we may need an end condition

def factorial(n):
	if n != 0:
		return n * factorial(n-1)
	else:
		return 1

print(factorial(0))
print(factorial(2))
print(factorial(3))
print(factorial(5))

Asking Using Recursion

Let's try to reimplement a program that continues to ask a question until the user says no by using recursion rather than a loop (how does the loop version go again?). →

Type "no" to stop
> yup
Type "no" to stop
> no

def ask_for_input():
    if input("Type \"no\" to stop\n> ") != "no":
        ask_for_input()
    else:
        # else is not necessary, but left in for clarity
        return

ask_for_input()

A Tree

Let's try to draw a tree using recursion. →

import turtle

leo = turtle.Turtle()
wn = turtle.Screen()
def branch(t, length, length_multiplier, min_length):
	if length < min_length:
		return
	else:
		t.forward(length)
		t.left(30)
		branch(t, length * length_multiplier, length_multiplier, min_length)
		t.right(60)
		branch(t, length * length_multiplier, length_multiplier, min_length)
		t.left(30)
		t.back(length)
		return
# base - branch(leo, , 0.6, 10)
branch(leo, 80, 0.6, 10)
wn.mainloop()

More Trees

import random
import turtle
t = turtle.Turtle()
wn = turtle.Screen()
wn.tracer(0)

t.left(90)

"""
add functions here
draw_tree
forest
"""

forest()
wn.mainloop()

draw_tree

def draw_tree(s, w):
    if s <= 5:
        return
    else:
        new_w = w if w <= 1 else w - 1
        t.pensize(w)
        a1 = random.randint(20, 50)
        t.forward(s)
        t.left(a1)
        draw_tree(s - random.randint(2, s // 2), new_w)
        a2 = random.randint(20, 50)
        t.right(a1 + a2)
        draw_tree(s - random.randint(2, s // 2), new_w)
        t.left(a2)
        t.back(s)

forest

def forest():
	for x in range(-300, 301, 200):
    	print(x)
    	t.up()
    	t.goto(x, -100)
    	t.down()
    	t.color("#{}".format(str(random.randint(0, 6)) * 3))
    	draw_tree(random.randint(30, 100), random.randint(4, 10))