Topic #17 – Recursion and More Sorting¶ Recursion¶

1def fact(n):
2    if n == 1:
3        return 1
4    else:
5        return n * fact(n-1)
6
7print(fact(5))

Activity

Test this code. What’s the answer? Why is that the answer? Trace through this code.

There is nothing really special happening here; we’re following the same rules we always have.

Don’t Panic¶

• Before talking about the next few things, I want you to be very well aware that these algorithms are outside the scope of this course

• I am showing you clever algorithms

• Probably the most sophisticated we’ve seen so far

• For now, don’t get distracted by all the details, just think about the big picture.

• The takeaway from this is to get a feel for how neat algorithms can get.

Quicksort¶

High Level¶

• An empty list, or a list with one thing in it, is already sorted, right?

• If I take a sorted list of things less than a number x, and a sorted list of things greater than a number x, then I can just do this:

[less than x] + [x] + [greater than x]

• This will also result in a sorted list, right?

Less high level¶

• You give me a list called in_list

• If the list has only one element (or none), just return the list without doing anything
• because it is a sorted list — DONE!

• I pick an element from the list, which I’ll call the pivot

• I partition the list by shuffling the elements around so that:
• all elements less than pivot are to the left of pivot

• all elements greater than pivot are to the right of it

• I recursively call quicksort on two lists:
• The list of stuff to the left of pivot

• The list of stuff to the right of pivot

1def partition(list, l, e, g):
2    while list != []:
5            l = [head] + l
7            g = [head] + g
8        else:
9            e = [head] + e
10    return (l, e, g)
11
12def quicksort(list):
13    print(list)
14    if list == []:
15        return []
16    else:
17        pivot = list
18        less, equal, greater = partition(list[1:],[],[pivot],[])
19        return quicksort(less) + equal + quicksort(greater)

Mergesort¶

High Level¶

• An empty list, or a list with one thing in it, is already sorted, right?

• We can merge two sorted lists together into a new, bigger sorter list.

Less high level¶

• You give me a list, in_list with n elements

• I divide in_list into n sublists, each having 1 element.

• The sublists are now already sorted! (Any list with only one element is automatically sorted)

• I now begin merging sublists, to produce bigger (but still sorted) sublists:
• I compare the first element in one sublist to the first in the other

• Whichever is smaller goes into the merged list

• I now compare the second element in that list to the first element in the other list

• … and so on…

• I keep going until there is nothing left to merge (there’s only one big, sorted, list)

1def merge(left, right):
2    merged = []
3    l=0
4    r=0
5    while l < len(left) and r < len(right):
6        if left[l] <= right[r]:
7            merged.append(left[l])
8            l = l + 1
9        else:
10            merged.append(right[r])
11            r = r + 1
12
13    if l < len(left):
14        merged.extend(left[l:])
15    else:
16         merged.extend(right[r:])
17    return merged
18
19def mergesort(list):
20    if len(list) <= 1:
21        return list
22    else:
23        midpoint = int( len(list) / 2 )
24        left = mergesort(list[:midpoint])
25        right = mergesort(list[midpoint:])
26        return merge(left,right)

Self Reference¶

• Let’s say I have the following code:

1a = [5, 6, 7]
2a.append(a)

• What is the length of the list a?

• What is in the list at index 3?

• What’s at a?

• What’s at a?

• Remember how things got kinda’ interesting when we start dealing with self-references?

• Is the following statement True of False?

This statement is False

• What happens when Pinocchio says

My nose is going to grow now

• Autological and Heterological words
• An autological word is one that describes itself
• English

• unhyphenated

• pentasyllabic

• A heterological word is one that does not describe itself
• French

• hyphenated

• monosyllabic

• If you’re lost, just ask yourself: Is the word English English? Is the word unhyphenated unhyphenated? Is the word hyphenated hyphenated?

• Seems reasonable to say that we can clearly categorize all the words as either autological or heterological.

• Let’s put them into Set_A or Set_H

• Where do we put the word round?

Is the word round round?

• Where do we put the word writable?

Is the word writable writable?

• Where do we put the word harmless?

Is the word harmless harmless?

• Where do we put the word autological?

Is the word autological autological?

• Hmmmmmm

• Weird one…

• A little different than the previous

• If it is, it is.
• If it’s autological, then it is autological and belongs in the set of autological words.

• If it’s not, it’s not…
• If it’s not autological, then it is heteroligical and it belongs in the set of heterological words.

• Where do we put the word heterological?

Is the word heteroligical heteroligical?

• Let’s start by saying the answer to this question is yes.
• If it is, then the word is describing itself.

• Therefore, the word heterological must be heterological

• What does it mean for a word to be heterological?

• Well, for a word to be heterological, it must not be describing itself.

• So if the word heteroligical is heterological, it must not be describing itself, and therefore it isn’t autological…

• For the heterological to be autological, it must be heteroligical, which would make it not autological.

• Is it then heteroligical?
• So if it does not describe itself, then that means that the word does not describe itself.

• Wait a min… that’s the definition of the word heterological…

• If the word heterological is heteroligical, it is therefore autological, which would mean that it’s not heteroligical…

Halting Problem¶

Activity++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Can you write a Python program that will look at a Python function and determine if the function might go into an infinite loop (does not halt)?

• Let’s assume the answer to this activity is “yes” and see where that gets us.

1def halt(f, i):
2    if f(i) halts:
3        return True
4    else:
5        return False
• Given this, I can easily do this:

1def problem0(f):
2    if halt(f, f) returns True:
3        # Go into an infinite loop
4        while True:
5            pass
6    else:
7        return False
• This may seem weird (it is), but it’s totally legal, right?

• What happens if I call problem0(problem0)?

• Let’s see what happens:

problem0(problem0) –> halt(problem0, problem0) –> problem0(problem0)

• Ok, let’s simplify this by asking 2 small questions:
• What would cause problem0(problem0) to go into an infinite loop?
• That would mean that halt(problem0, problem0) returned True, which means halt said that the program halted.

• Looking into halt, this happens when f(i) halts.

• In our case, f is problem0 and i is problem0

• So, when problem0(problem0) halts.

• Wait… problem0(problem0) goes into an infinite loop when problem0(problem0) does not go into an infinite loop.

• Ok, we’ve got a problem here. So let’s just ignore this and ask the other question and hope my day isn’t ruined.

• What would cause problem0(problem0) to not go into an infinite loop?
• That would mean that halt(problem0, problem0) returned False

• This will happen when problem0(problem0) does not go into an infinite loop

• I give up.

Why is this interesting?

• Humans want to be able to ask the question

Given these premises, can we get a specific conclusion?

• This shows us that, given our computational model, there are some things that we just can not compute.