Previous Lecture Lecture 7 Next Lecture

Lecture 7, Thu 10/19

Recursion, Python Lists vs. Dictionaries

Recorded Lecture: 10_19_23

Recursion

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

Common Example: Factorial

def factorial(n):
	if n == 0:      # base case
		return 1
	return n * factorial(n-1)

Function Calls and the Stack

def double(n):
	return 2 * n

def triple(n):
	return n + double(n)

print(triple(5))

triple.png

factorial.png

Common Example: Fibonnaci Sequence

def fibonnaci(n):
	if n == 1:    # base cases
		return 1
	if n == 0:          
		return 0

	return fibonnaci(n-1) + fibonnaci(n-2)

fib(3)                    +  fib(2)
fib(2)          + fib(1)  +  fib(2)
fib(1) + fib(0) + fib(1)  +  fib(2)
1      + fib(0) + fib(1)  +  fib(2)
1      + 0      + fib(1)  +  fib(2)
1      + 0      + 1       +  fib(2)
1      + 0      + 1       +  fib(1) + fib(0)
1      + 0      + 1       +  1      + fib(0)
1      + 0      + 1       +  1      + 0
3

Python Lists vs. Python Dictionaries

# Set up our data structures
DICT = {}
infile = open("wordlist.txt", 'r')
for x in infile: # x goes through each line in the file
	DICT[x.strip()] = 0 # Creates an entry in DICT with key x.strip() and value 0
print(len(DICT))
infile.close() # close the file after we’re done with it.

WORDLIST = []
for y in DICT: # put the DICT keys into WORDLIST
	WORDLIST.append(y)
print(len(WORDLIST))

# Algorithm 1 - Lists
from time import time
start = time()
infile = open("PeterPan.txt", 'r')
largeText = infile.read()
infile.close()
counter = 0
words = largeText.split()
for x in words:
	x = x.strip("\"\'()[]{},.?<>:;-").lower()
	if x in WORDLIST:
		counter += 1
end = time()
print(counter)
print("Time elapsed with WORDLIST (in seconds):", end - start)

# Algorithm 2 - Dictionaries
start = time()
infile = open("PeterPan.txt", 'r')
largeText = infile.read()
infile.close()
words = largeText.split()
counter = 0
for x in words:
	x = x.strip("\"\'()[]{},.?<>:;-").lower()
	if x in DICT: # Searching through the DICT
		counter += 1
end = time()
print(counter)
print("Time elapsed with DICT (in seconds):", end - start)