1 of 67

Recursion

Jake Shoudy

Nov 16, 2022

CSCI 110 - Lecture 32

2 of 67

Announcements

3 of 67

Career week!

All recordings/slides available here (also on class website)

PLEASE fill out quick feedback form for each talk you attended

Log your own PD hours via the links here

4 of 67

Quiz 10

Last quiz this Friday!

Meet in lab downstairs

Will cover Classes and sorting

5 of 67

HW10

Last assignment

Classes and sorting

Due Monday November 21st at 11:59pm

6 of 67

Final Exam Date!

Tuesday 11/29 during normal lab hours

8-10am
12:30-2:20pm
3-4:50pm

7 of 67

Final Exam Topics

Binary <-> Base 10

Data types

Operators (arithmetic, comparison, logical)

Variables

if / elif / else

while loops

Strings (length, index, slice)

Functions

For Loops

Will include short answer & coding questions

Lists

2D Lists

Big O

Sets

Dictionaries

Nested Dictionaries

Scope

Pass by Reference vs Pass by Value

Classes

Sorting

8 of 67

Reminder: NO CLASS NEXT WEEK

Cancelling class on Monday and Tuesday

Wednesday - Friday are school holidays

There will be a Kahoot review session on Monday the 28th

9 of 67

Recap

10 of 67

.sort()

sorted()

Instance method
Only works on lists
Mutates the lists when sorting
Is a void function (returns None)

Function
Works on any iterable (dictionary, list, set, string)
Does not mutate
Returns a list with the iterable values sorted

Sort in ascending order by default
Can reverse the order of sorting with `reverse=True` parameter
Can customize the sort order with the `key=function name` parameter

11 of 67

Sorting students

students = [[‘Nirmal’, 39], [‘Michael’, 18], [‘Jeremy’, 19], [‘Constance’, 18], [‘Andre’, 19], [‘Deirdre’, 18], [‘Zade’, 19], [‘Conner’, 18]]

students.sort()

[[‘Andre’, 19], [‘Conner’, 18], [‘Constance’, 18], [‘Deirdre’, 18], [‘Jeremy’, 19], [‘Michael’, 18], [‘Nirmal’, 39], [‘Zade’, 19]]

12 of 67

Sorting students by age

students = [[‘Nirmal’, 39], [‘Michael’, 18], [‘Jeremy’, 19], [‘Constance’, 18], [‘Andre’, 19], [‘Deirdre’, 18], [‘Zade’, 19], [‘Conner’, 18]]

students.sort(key=lambda student : student[1])

[[‘Michael’, 18], [‘Constance’, 18], [‘Deirdre’, 18], [‘Conner’, 18], [‘Jeremy’, 19], [‘Andre’, 19], [‘Zade’, 19], [‘Nirmal’, 39]]

13 of 67

Using name as a secondary “tie breaker”

students = [[‘Nirmal’, 39], [‘Michael’, 18], [‘Jeremy’, 19], [‘Constance’, 18], [‘Andre’, 19], [‘Deirdre’, 18], [‘Zade’, 19], [‘Conner’, 18]]

students.sort(key=lambda student : (student[1], student[0]))

[[‘Conner’, 18], [‘Constance’, 18], [‘Deirdre’, 18], [‘Michael’, 18], [‘Andre’, 19], [‘Jeremy’, 19], [‘Zade’, 19], [‘Nirmal’, 39]]

14 of 67

Using name as a secondary “tie breaker” v2

students = [[‘Nirmal’, 39], [‘Michael’, 18], [‘Jeremy’, 19], [‘Constance’, 18], [‘Andre’, 19], [‘Deirdre’, 18], [‘Zade’, 19], [‘Conner’, 18]]

students.sort(key=lambda student : student[0])

[[‘Andre’, 19], [‘Conner’, 18], [‘Constance’, 18], [‘Deirdre’, 18], [‘Jeremy’, 19], [‘Michael’, 18], [‘Nirmal’, 39], [‘Zade’, 19]]

students.sort(key=lambda student : student[1])

[[‘Conner’, 18], [‘Constance’, 18], [‘Deirdre’, 18], [‘Michael’, 18], [‘Andre’, 19], [‘Jeremy’, 19], [‘Zade’, 19], [‘Nirmal’, 39]]

15 of 67

Sort by age descending

students = [[‘Nirmal’, 39], [‘Michael’, 18], [‘Jeremy’, 19], [‘Constance’, 18], [‘Andre’, 19], [‘Deirdre’, 18], [‘Zade’, 19], [‘Conner’, 18]]

students.sort(key=lambda student : (student[1], student[0]), reverse=True)

[[‘Nirmal’, 39], [‘Zade’, 19], [‘Jeremy’, 19], [‘Andre’, 19], [‘Michael’, 18], [‘Deirdre’, 18], [‘Constance’, 18], [‘Conner’, 18]]

16 of 67

Sorting Runtime

Different sorting algorithms also have different runtimes.

The default sort in every programming language has time complexity:

O(n log(n))

17 of 67

Recursion

18 of 67

Calling functions from other functions

def add_one(num):

return num + 1

def add_five(num):

for i in range(5):

num = add_one(num)

return num

print(add_five(10))

15

19 of 67

Calling functions from within that function

def add_one(num):

num = add_one(num) + 1

return num

print(add_one(10))

RecursionError: maximum recursion depth exceeded

20 of 67

Imagine you are waiting in a line…

21 of 67

Imagine you are waiting in a line…

How do you determine how long the line is?

You could just get out of line and count!

22 of 67

What if it is a really long line?

23 of 67

Imagine you are waiting in a line…

How do you determine how long the line is?

You could still count! But it might take awhile…

What if no one will save your spot in line? Getting out of line would make you have to go to the end :/

It is too far to see the entire line from where you are standing

24 of 67

Idea!

Recursion

recursion: defining a problem in terms of itself.
recursive programming: Writing methods that call themselves to solve problems recursively.

An equally powerful substitute for iteration (loops)
Particularly well-suited to solving certain types of problems

37 of 67

Recursion

Every recursive algorithm involves at least 2 cases:

base case: A simple occurrence that can be answered directly.
recursive case: A more complex occurrence of the problem that cannot be directly answered, but can instead be described in terms of smaller occurrences of the same problem.

Some recursive algorithms have more than one base or recursive case, but all have at least one of each. – A crucial part of recursive programming is identifying these cases

38 of 67

How long is the line?

def line_length(person):

if (you are first in line):

return 1

else:

# ask neighbor what position they are in and wait

# for their response. Add 1

return line_length(neighbor) + 1

Base Case

Recursive Case

39 of 67

Fibonacci

40 of 67

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1

41 of 67

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

0

1

42 of 67

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

1

1,

2

43 of 67

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

1

2

1,

2,

3

44 of 67

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

2

3

1,

2,

3,

5

45 of 67

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

3

5

1,

2,

3,

5,

8

46 of 67

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

5

8

1,

2,

3,

5,

8,

13

47 of 67

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

8

13

1,

2,

3,

5,

8,

13,

21

48 of 67

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1, 1, 2, 3, 5, 8, 13, 21...

49 of 67

Code Fibonacci Sequence

Function: fibonacci()

Input: number n

Output: nth value in Fibonacci Sequence

Examples:

fibonacci(0) -> 0

fibonacci(1) -> 1

fibonacci(2) -> 1

fibonacci(3) -> 2

fibonacci(4) -> 3

fibonacci(5) -> 5

fibonacci(6) -> 8

fibonacci(7) -> 13

50 of 67

Code using a loop

def fibonacci(num):

if num <= 1:

return num

num_1 = 0

num_2 = 1

for i in range(num - 1):

temp = num_2

num_2 = num_2 + num_1

num_1 = temp

return num_2

51 of 67

Thinking recursively

Can I define this problem in terms of itself?

Hint: what if I start from the top instead of from the bottom?

fibonacci(4) -> 3

fibonacci(5) -> 5

fibonacci(6) -> 8

fibonacci(7) -> 13

fibonacci(0) -> 0

fibonacci(1) -> 1

fibonacci(2) -> 1

fibonacci(3) -> 2

52 of 67

Thinking recursively

f(5) = f(4) + f(3)

f(3) + f(2)

f(2) + f(1)

f(1) + f(0)

53 of 67

Thinking recursively

f(5) = f(4) + f(3)

f(3) + f(2)

f(2) + f(1)

f(1) + f(0)

54 of 67

Thinking recursively

f(5) = f(4) + f(3)

f(3) + f(2)

f(2) + 1

1 + 0

55 of 67

Thinking recursively

f(5) = f(4) + f(3)

f(3) + 1

1 + 1

56 of 67

Thinking recursively

f(5) = f(4) + 2

2 + 1

57 of 67

Thinking recursively

f(5) = 3 + 2

58 of 67

Thinking recursively

f(5) = 5

59 of 67

Code Fibonacci Sequence

def fibonacci(n):

if n <= 1:

return n

else:

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

Base Case

Recursive Case

60 of 67

Motivation

61 of 67

Why learn recursion?

A challenge! A different way of thinking of problems
Can solve some kinds of problems better than iteration
Leads to elegant, simplistic, short code (when used well)
Some programming languages ("functional" languages such as Scheme, ML, and Haskell) use recursion exclusively (no loops)

It’s beautiful!!

62 of 67

Population count

def update_population_count(population):

world_population = 0

for continent in population:

continent_population = 0

for country in population[continent]:

country_population = 0

for state in population[continent][country]:

state_population = 0

for city in population[continent][country][state]:

state_population += population[continent][country][state][city]

population[continent][country][state]['total'] = state_population

country_population += state_population

population[continent][country]['total'] = country_population

continent_population += country_population

population[continent]['total'] = continent_population

world_population += continent_population

population['total'] = world_population

63 of 67

Population count

def update_population_count(population):

if type(population) != dict:

return population

else:

total = 0

for key in population:

total += update_population_count(population[key])

population['total'] = total

return total

64 of 67

Recursion in Nature (Self Similarity)

65 of 67

Recursion in Nature (Self Similarity)

66 of 67

Recursion in Nature (Self Similarity)

67 of 67

Recursive art!

http://recursivedrawing.com/

Try this!