Recursion¶

CS 66: Introduction to Computer Science II

References for this lecture¶

Problem Solving with Algorithms and Data Structures using Python

Sections 5.1-5.8 https://runestone.academy/ns/books/published/pythonds/Recursion/toctree.html

Wrapping up Hash Tables¶

The hash tables we made will only store integers

Can you think of a strategy that will allow us to put strings in a table?

0:[]
1:[]
2:[]
3:['Dr. Mario']
4:[]
5:['Pikachu', 'Kirby']
6:['Sheik', 'Mr. Game and Watch']
7:['Dr. Carlson', 'Jiggly Puff']
8:['Captain Falcon']
9:['Mew Two']

these are the names my kids gave our chicks that just hatched

In [ ]:

Built-in Hash Function¶

Python contains a built-in hash function that you can use.

Be careful, the hash is somewhat randomized and values change every time you re-start your code (this brings issues with saving hashed values to a file, etc.)

In [ ]:
print( hash("Star Wars: Episode VII - The Force Awakens (2015)") )

Map ADT¶

Hash tables are also often used to implement the map abstract data type

A map abstract data type stores key-value pairs and allows you to use a key to look up its associated value.

A Python dictionary is a map.

There are other data structures you could use to implement a map, such as a list of tuples.

The following is the book's definition of the Map ADT:

  • Map() Create a new, empty map. It returns an empty map collection.
  • put(key,val) Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.
  • get(key) Given a key, return the value stored in the map or None otherwise.
  • del Delete the key-value pair from the map using a statement of the form del map[key].
  • len() Return the number of key-value pairs stored in the map.
  • in Return True for a statement of the form key in map, if the given key is in the map, False otherwise.

Chained Hash Map¶

We could use a similar strategy that we used for set, but store (key,value) tuples

0:[(20, 'chicken')]
1:[(31, 'cow')]
2:[]
3:[(93, 'lion')]
4:[(54, 'cat'), (44, 'goat')]
5:[(55, 'pig')]
6:[(26, 'dog')]
7:[(17, 'tiger'), (77, 'bird')]
8:[]
9:[]

(maybe this is a map that a zoo uses to look up which animal has each id)

Textbook's Linear-Probed-Hash-Table Map¶

The following code shows the start of the book's approach to using a Hash Table with linear probing to implement a map.

self.slots list stores the keys

self.data stores the associated values

In [ ]:
class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size
        
    def put(self,key,data):
        hashvalue = self.hashfunction(key,len(self.slots))

        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        else:
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data  #replace
            else:
                nextslot = self.rehash(hashvalue,len(self.slots))
            while self.slots[nextslot] != None and self.slots[nextslot] != key:
                nextslot = self.rehash(nextslot,len(self.slots))

            if self.slots[nextslot] == None:
                self.slots[nextslot]=key
                self.data[nextslot]=data
            else:
                self.data[nextslot] = data #replace

    def hashfunction(self,key,size):
         return key%size

    def rehash(self,oldhash,size):
        return (oldhash+1)%size

Recursion¶

a recursive function is a function that calls itself.

Recursion is also a problem solving strategy that allows you to solve problems by breaking them down to smaller and smaller sub-problems, which are eventually trivial to solve.

It can be hard to think recursively at first, but when you get good at it, it will allow you to solve some problems in really elegant ways.

Group Activity Problem 1¶

Copy this function into a .py file and run it. It will eventually result in an error - wait for it.

Read the error message you get. Discuss in your groups:

  1. What is the difference between this and an infinite loop?
  2. Why did this result in an error when an infinite loop would just go on forever?
In [ ]:
def recursive_hello():
    print("hello")
    recursive_hello()
    
recursive_hello()

Then try this version:

In [ ]:
def recursive_hello(n):
    if n > 0:
        print("hello")
        recursive_hello(n-1)
        
recursive_hello(5)

Discuss:

  1. What causes this one to stop when the first version didn't?
  2. What does the parameter, n do in this version?
  3. Why did the programmer put n-1 in for the argument in the recursive call?

Recursive problem solving example¶

Let's revisit the sum-of-n problem we previously solved in different ways. The goal is to write a function that will compute

$$1+2+3+\cdots+(n-1)+n$$

We might start by breaking $1+2+3+\cdots+(n-1)+n$ into two parts:

$$1+2+3+\cdots+(n-1)$$

and

$$n$$

Notice that $1+2+3+\cdots+(n-1)$ is just a smaller version of the original problem! So, a recursive solution might look like this:

In [ ]:
def sum_of_n(n):
    result = sum_of_n(n-1) + n
    return result

There's a problem: this one has no way to stop.

To get it to stop, we need to think about what our base case - the smallest case, when the problem is simple. For sum-of-n, it could be when n is 0.

The sum of all numbers up to 0 is just 0, so we add this into our code:

In [ ]:
def sum_of_n(n):
    if n == 0:
        return 0
    else:
        result = sum_of_n(n-1) + n
        return result

The Three Laws of Recursion¶

  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.

Group Activity Problem 2¶

The factorial of a number (often denoted in math as $n!$) is defined as

$$ n! = 1 * 2 * 3 * \cdots * (n-1) * n $$

Here's some code which attempts to solve it recursively, but it is missing a base case. Discuss what the base case should be, and then add it to the code.

In [ ]:
def factorial(n):
    result = n * factorial(n-1)
    return result

Group Activity Problem 3¶

The following is an approach to finding the sum of a list of numbers. The idea that this programmer came up with is to notice that the sum of a list like [1,3,5,7,9] is the same as 1 plus the sum of [3,5,7,9]. The base case happens when there is only one item in the list. The programmer has written part of this but is stuck on the recursive call. Fill in the blank for them.

In [ ]:
def listsum(num_list):
    if len(num_list) == 1:
        return num_list[0]
    else:
        return num_list[0] + #fill in the blank

Group Activity Problem 4¶

The code below is a variation of the UnorderedList implementation we've been working on, except the search function has been replaced with a new recursive version. Run the code and make sure it works, then answer the following questions:

  1. There's more than one base case - what are they?
  2. Notice that the __search_node method has a parameter called currnode. What is currnode and why does it have to be a parameter?
  3. Why is there both a search and a __search_node method? Why do you think __search_node has been named with two underscores?
In [ ]:
class Node:
    def __init__(self,initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

class UnorderedList:

    def __init__(self):
        self.head = None
        self.length = 0
        
    def isEmpty(self):
        return self.head == None
        
    def size(self):
        return self.length

    #this method is really a prepend - it puts the new node at the beginning
    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
        self.length += 1
            
    def __repr__(self):
        list_representation = ""
        current = self.head #start with the Node at the head
        while current: #this will keep going until current equals None
            list_representation += str(current.getData())+" -> "
            current = current.getNext() #move on to the next Node in the list
        list_representation += "None" #the last one in the list points to None
        return list_representation

    def __contains__(self,item):
        return self.search(item)
    
    ############################
    ### New code starts here ###
    ############################
    
    def search(self,item):
        return self.__search_node(item,self.head)
    
    def __search_node(self,item,currnode):
        #if we're at the end of the list return False - it isn't here
        if currnode == None:
            return False
        #we found the item - return True
        elif currnode.getData() == item:
            return True
        #search the rest of the list
        else:
            return self.__search_node(item,currnode.getNext())
        


my_list = UnorderedList()

my_list.add(31)
my_list.add(77)
my_list.add(17)
my_list.add(93)
my_list.add(26)
my_list.add(54)

print( my_list.search(17) )
print( my_list.search(13) )

Group Activity Problem 5¶

You can write an index method which calls a recursive __index_node method in a similar way to search and __search_node. What changes would you need to make for that to work?

Turtle Graphics¶

The turtle graphics package is a fun way to create drawings by giving commands that describe how a pencil (or a turtle) should move around on a piece of paper.

Documentation: https://docs.python.org/3/library/turtle.html

Example:

In [ ]:
import turtle

my_turtle = turtle.Turtle()
my_win = turtle.Screen()

my_turtle.forward(100)
my_turtle.right(90)
my_turtle.forward(50)
my_turtle.right(45)
my_turtle.forward(200)
my_turtle.left(30)
my_turtle.forward(50)

turtle.exitonclick()

Group Activity Problem 6¶

Write some additional turtle instructions to see if you can it to move back where it started.

Group Activity Problem 7¶

Run the following recursive function which draws a spiral. Discuss in your groups:

  1. What does the 90 do?
  2. What does it include lineLen-5?
  3. What is the base case of this recursive function?

Then, change the 90 to 45. What does that do? Can you adjust the code to make the spiral look like a smooth curve?

In [ ]:
import turtle

myTurtle = turtle.Turtle()
myWin = turtle.Screen()

def drawSpiral(myTurtle, lineLen):
    if lineLen > 0:
        myTurtle.forward(lineLen)
        myTurtle.right(90)
        drawSpiral(myTurtle,lineLen-5)

drawSpiral(myTurtle,100)
myWin.exitonclick()