2 of 76

Today’s Agenda

	Review (Sorting) Recursion

4 of 76

sort()

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

5 of 76

sorted()

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

6 of 76

Both sort() & 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

7 of 76

Sorting students by name

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]]

8 of 76

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]]

9 of 76

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]]

10 of 76

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]]

11 of 76

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]]

12 of 76

Sorting Runtime

Different sorting algorithms also have different runtimes.

The default sort in every programming language has time complexity:

O(n log(n))

13 of 76

Recursion

14 of 76

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 of 76

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

16 of 76

Imagine you are waiting in a line…

17 of 76

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!

18 of 76

What if it is a really long line?

19 of 76

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...

20 of 76

Idea!

Ask your neighbor! Maybe they know?

Hey do you know how long this line is?

21 of 76

Idea!

Nope but I can ask!

22 of 76

Idea!

Hey do you know how long this line is?

23 of 76

Idea!

Nope but I can ask!

24 of 76

Idea!

Hey do you know how long this line is?

25 of 76

Idea!

Nope but I can ask!

26 of 76

Idea!

Hey do you know how long this line is?

27 of 76

Idea!

Yes i’m actually first in line!

28 of 76

Idea!

I’m second in line!

29 of 76

Idea!

I’m third in line!

30 of 76

Idea!

I’m fourth in line!

31 of 76

Idea!

I guess I’m fifth!

32 of 76

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!

33 of 76

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!

34 of 76

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, wait for response, add 1

return line_length(neighbor) + 1

Base Case

Recursive Case

35 of 76

Factorial

36 of 76

Code Factorial (iteratively = using a loop)

Function: factorial()

Input: number n

Output: n!

Examples:

factorial(0) -> 1

factorial(1) -> 1

factorial(2) -> 2 * 1 = 2

factorial(3) -> 3 * 2 * 1 = 6

37 of 76

Code using a loop

def factorial_iterative(n):

if n < 0:

raise ValueError("n cannot be negative")

elif n == 0:

return 1

else:

result = 1

for i in range(1, n + 1):

result = result * i

return result

38 of 76

Code Factorial (using recursion)

Function: factorial()

Input: number n

Output: n!

Examples:

factorial(0) -> 1

factorial(1) -> 1

factorial(2) -> 2 * factorial(1) = 2

factorial(3) -> 3 * factorial(2) = 6

39 of 76

Code using recursion

def factorial(n):

if n < 0:

raise ValueError("n cannot be negative")

if n == 0 or n == 1:

return 1

else:

return n * factorial(n - 1)

40 of 76

Fibonacci

41 of 76

Fibonacci Sequence