CS 2120: Class #15
====================
Some things
^^^^^^^^^^^
.. image:: ../img/hands.jpg
* `Gould playing Bach <https://www.youtube.com/watch?v=Mia9woisQZo>`_
* Let's draw a `Koch Snowflake <http://en.wikipedia.org/wiki/Koch_snowflake>`_ on the board.
* Let's write a program that does this::
Let the user pick some complex parameter c
For every complex number (r,i) in a bounded plane:
z = c
while z is not *really big*:
z = z*z + c
if z has convereged, this point is 'in'
this point is 'out'
* (Mathematically, of course, *really big* isn't enough, we're looking for
values that diverge to infinity... but Python doesn't do infinity so well,
so here we are)
* A full Python version is `here <http://www.scipy.org/Tentative_NumPy_Tutorial/Mandelbrot_Set_Example>`_
* Let's plot that set (black dot for elements in the set, coloured dot otherwise -- colour indicating how fast the value goes to infinity), and then zoom in on it: `Mandlebrot zoom <http://vimeo.com/6035941>`_
.. admonition:: Activity
What do all of these things (The Escher Drawing, the Bach Fugue, the fractals)
have in common?
.. admonition:: Activity
What does the following Python code do. Try to figure it out *without* running
it. What's new about how it works?::
def my_func(n):
if n < 1 :
return 0
else:
return n + my_func(n-1)
* We have discovered *recursion*.
* Hold onto your hats folks!
* Let's go back and trace the execution of our function on the board
(pencil & paper debug) for a test case.
.. admonition:: Activity
Fill out the instructor evaluations!
.. Warning::
Pay really close attention here. The intuition we're going to gain from
walking through this simple example is critical.
Recursion
^^^^^^^^^^
* If a function calls *itself*, it is said to be a *recursive function*.
* You've seen recursion before in your math classes (e.g., recurrence relations)
* Why would you want to have a function call itself??
* Well, maybe you want to repeat a section of code multiple times...
* ... like a loop!
* Anywhere you can use a loop, you could also use recursion. The underlying
effect is the same: repeating a chunk of code multiple times.
* The *semantics* of how that happens are a bit different.
* Some languages (e.g., Scheme) *forbid* loops and allow only recursion.
* Some languages (e.g., Fortran 77) *forbid* recursion and allow only loops.
* Most allow both because some problems are easier to solve with loops...
and some are easier to solve with recursion.
* There is *nothing* that can be done with recursion that can't be done with
loops (and vice-versa). This is a mathematically provable *theorem*.
* However, some things are *a lot easier* with one or the other.
Thinking Recursively
^^^^^^^^^^^^^^^^^^^^^
* To really "think recursively" requires us to rewire ourselves a bit.
* Recursion is, without question, the most difficult CS1 topic for most students.
* If you're frustrated, stop me and ask questions.
* Recursion is so incredibly powerful in some instances, that you simply can't
be a good programmer without mastering it. But that takes time. Expect frustration.
.. raw:: html
<iframe width="560" height="315" src="https://www.youtube.com/embed/TAffSQmTHVs" frameborder="0" allowfullscreen></iframe>
The dark side of recursion
^^^^^^^^^^^^^^^^^^^^^^^^^^^
.. * Once again, with incredible power comes incredible responsibility.
.. image:: ../img/spiderman.jpg
.. admonition:: Activity
I've modified the function we wrote above to add up only every *other* number.
Try running this new version with the call ``my_func(8)``.
Now try: ``my_func(7)``. What happened? Can you figure out how to fix it? (assuming you didn't want this to happen)::
def my_func(n):
if n == 0:
return 0
else:
return n + my_func(n-2)
.. image:: ../img/stackOverflow.jpg
Writing a simple recursive function
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
* I'm going to give you some rules for writing recursive functions.
* By following these rules, we can avoid the catastrophe we just had.
* (When you get sophisticated enough, you'll find situations in which it's OK to stretch/violate these rules.)
* Every recursive function needs two things:
* A **base case** that *terminates* the recursion.
* A **recursive step** that calls the function again, but with a modified (probably smaller) parameter.
.. admonition:: Activity
Identify the **base case** and **recursive step**
in this function::
def my_func(n):
if n < 1 :
return 0
else:
return n + my_func(n-1)
Now it's your turn:
.. admonition:: Activity
Using "the rules", write a function ``fact(n)`` which computes the factorial
of ``n`` *using recursion* (no loops allowed!!). Remember that factorial
is defined as n! = n * (n-1) * (n-2) * ... * 2 * 1. So, for example,
5! = 5 * 4 * 3 * 2 * 1 = 120 .
* `Use this website for a nice visualization! <http://www.pythontutor.com/visualize.html#mode=display>`_
Recursive Data Structures
^^^^^^^^^^^^^^^^^^^^^^^^^^
* Recursive algorithms often work best with "recursive data structures".
* Recursive data structures break down similarly to our approach to recursive algorithms:
* **base case** : a single piece of data (e.g., an integer)
* **recursive case** : *everything else* in the data structure
.. admonition:: Activity
So far, we've been thinking of lists as collections of values. Try to come up
with a *recursive* formulation for a list.
* Got it? Good.
.. admonition:: Activity
Write a function ``sum_list(l)`` that will return the sum of adding up
all of the elements of ``l``. You *may not* use loops! Assume that ``l``
is a list of integers.
* We can think of lists as recursive, or non-recursive, data structures, depending
on what we're trying to do with them.
* This is true for *any* data structure, though some are much more naturally
thought of in one way or the other.
Quicksort
^^^^^^^^^^^
* You give me a list called ``inlist``
* If the list has only one element, just return the list without doing anything
* 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``
.. admonition:: Activity
Do a quicksort, with pencil and paper, on the list ``[3,7,15,9,4,11,1,5,2]``.
Record the value of your list at each step.
* You can see why we waited to study Quicksort.
* The idea of recursion is *central* to the description
* You can, of course, *implement* quicksort without using recursion, but it's a bit uglier.
* Thinking recursively, it's a very clean divide-and-conquer strategy.
* Let's try it::
def partition(list, l, e, g):
while list != []:
head = list.pop(0)
if head < e[0]:
l = [head] + l
elif head > e[0]:
g = [head] + g
else:
e = [head] + e
return (l, e, g)
def quicksort(list):
from random import choice
print list
if list == []:
return []
else:
pivot = list[0]
less, equal, greater = partition(list[1:],[],[pivot],[])
return quicksort(less) + equal + quicksort(greater)
.. admonition:: Activity
Modify the ``quicksort()`` function above so that it prints out the value of ``list`` every time it is called.
Try sorting a few lists and following the output.
.. admonition:: Activity
What is the **base case** in ``quicksort()`` ?
What is the **recursive case**?
There are *no loops*... so how do I figure out how long it takes to sort a list with ``n`` elements? In the worst case? In the average case? Do you think this is a good sort? How does it compare to selection or insertion sort?
* A definite improvement, but still not great in the worst case. Can we do better?
.. raw:: html
<iframe width="560" height="315" src="https://www.youtube.com/embed/kqWLdhLxpzs" frameborder="0" allowfullscreen></iframe>
Mergesort
^^^^^^^^^^
* You give me a list, ``inlist`` with ``n`` elements
* I divide ``inlist`` 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)
.. admonition:: Activity
Do a mergesort, with pencil and paper, on the list ``[3,7,15,9,4,11,1,5,2]``.
Record the value of your list at each step.
* Let's start by implementing a ``merge`` operation in Python::
def merge(left, right):
merged = []
l=0
r=0
while l < len(left) and r < len(right):
if left[l] <= right[r]:
merged.append(left[l])
l = l + 1
else:
merged.append(right[r])
r = r + 1
if l < len(left):
merged.extend(left[l:])
else:
merged.extend(right[r:])
return merged
.. admonition:: Activity
Try merging some lists with ``merge``.
Remember: ``merge`` expects that the lists it is merging are *already sorted*!! If the lists to merge weren't already sorted, what would have to change about ``merge`` ?
* Okay, now the real deal::
def mergesort(list):
if len(list) <= 1:
return list
else:
midpoint = int( len(list) / 2 )
left = mergesort(list[:midpoint])
right = mergesort(list[midpoint:])
return merge(left,right)
* Wow, that was short! WTF is going on in there?
.. admonition:: Activity
Modify the ``mergesort()`` function above so that it prints out the value of ``list`` every time it is called.
Try sorting a few lists and following the output.
.. admonition:: Activity
What is the **base case** in ``mergesort()`` ? What is the **recursive case**? How many recursive calls will I make to ``mergesort()`` for a list of size ``n`` on average? In the worst case?
.. raw:: html
<iframe width="560" height="315" src="https://www.youtube.com/embed/NJoH6d1uAzk" frameborder="0" allowfullscreen></iframe>
Recursion
^^^^^^^^^^
* This has been a tiny taste of recursion.
* If you take more CS courses, you'll see more recursive algorithms and you'll
develop an intuition for when it's advantageous to use recursion.
* The official "learning goals" for this class though, are much more modest:
* Exposure to recursion
* Ability to define recursion
* Ability to recognize recursion in a Python function
* If you actually *understand* recursion with no effort, then you are *way* ahead of the curve
and should consider a CS major.
* If you don't totally "get it"... you're normal. Here's the secret to "getting it":
* Practice.
The even darker side of recursion
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
* Let's start with a warmup:
.. admonition:: Activity
Is the following statement true or false: "This statement is False."?
.. admonition:: Activity
What happens when Pinocchio says: "My nose is going to grow now."?
* And then get down to business...
.. admonition:: 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?
* Let's assume the answer to this activity is "yes" and see where that gets
us.
* Based on our assumption, I can write a function called ``youre_screwed(func)`` that takes some
arbitrary Python function ``func()`` as its input.
* If ``func()`` goes into an infinite loop, ``youre_screwed()``
prints "Infinite loop in ``func()`` " and ``returns``
* If ``func()`` doesn't go into an infinite loop, this (perverse)
function, ``youre_screwed()`` , *does* go into an infinite loop (I told you it was perverse).
* So... what happens if I execute:
>>> youre_screwed(youre_screwed)
* ???
* `HUH? <https://simple.wikipedia.org/wiki/Halting_problem>`_
.. image:: ../img/scared.jpeg