Here is the `isSorted(L)`

function from last class:

```
def isSorted(L):
"""return True if list is in sorted order, low to high"""
if len(L) <= 1:
return True
else:
# check L[0] vs L[1]
if L[0] > L[1]:
return False
else:
return isSorted(L[1:])
```

For the base case, we know the answer: a zero- or one-element list is
obviously sorted, so return `True`

.

For the non-base case, just check if the first two are in order. If not,
we can immediately say the list is not in order (`return False`

). If the
first two items *are* in order, make the leap of faith: `isSorted(L[1:])`

will give us a `True`

or a `False`

, if the rest of the list is sorted
or not, so just `return`

whatever we get back from that recursive call.

Finally, now that we understand recursion a little better, here are some examples that are "naturally recursive". These are algorithms that are easier/more elegant to write using recursion. Again, you could write them iteratively (using loops), but sometimes it makes more sense to use recursion (not always!).

Here is an interesting picture. Can you see the recursion? What happens first, and what is the base case?

Using
Zelle Graphics,
first write a function called `H(win, pt, size)`

that draws
a single "H" in the given graphics window, at the given Point `pt`

, with the
given `size`

. For example, calling `H(win,Point(100,100),50)`

would draw an
"H" at the coordinates `(100,100)`

with size `50`

.

For the "H" function, you will need to create `Line()`

objects using other
`Point()`

objects. Using the `clone()`

method will definitely help:

```
>>> from graphics import *
>>> pt = Point(100,100) # assume we are given these
>>> size = 50 # assume we are given these
>>>
>>> p1 = pt.clone()
>>> p1.move(-size,-size)
>>> p2 = pt.clone()
>>> p2.move(-size,size)
>>> leftedge = Line(p1,p2) # create left edge of the H
>>> leftedge.draw(win)
```

Once you have a working `H()`

function, can you use it to draw one "H",
then another at point `p1`

? And another at that H's `p1`

? And so on...

What is the base case for the recursion? What happens when the size gets
too small? Also, how many times do we need to recur to get the four H's
at the four corners (points `p1`

, `p2`

, and so on)?

There are many interesting examples of recursive graphics algorithms. Take a look at some of these links and see if you can understand how they recur:

- nodebox letters
- nodebox plants
- L-systems
- Anne M. Burns: Recursion in Nature...
- fern demo
- Princeton CS projects

Here is the `mergeSort()`

algorithm from last week:

```
def mergeSort(L):
"""use merge sort to sort L from low to high"""
if len(L) > 1:
# split into two lists
half = len(L)/2
L1 = L[0:half]
L2 = L[half:]
# sort each list
mergeSort(L1)
mergeSort(L2)
# merge them back into one sorted list
merge(L1,L2,L)
```

For this one, the base case is not explicitly written. It just does "nothing" if the length of the list is one or less.

Any *divide-and-conquer* algorithms, like the merge sort, can usually be expressed
easily using recursion.

Since merge sort simply divides the original list in half, then each subsequent
list in half, and so on, part of the big-O notation must be `logN`

, because that's
*how many times we can divide a list of size N in half*. The other part of merge
sort is to merge them all back together. Given two sorted lists, the merge operation
just compares the first items in each list. This will require *at most* `N`

compares,
so it's not hard to see that the **merge sort is an O(NlogN) algorithm**. This is

Here is a nice picture from wikipedia of what happens during the merge sort.

And here are some timings (for initially random lists of N integers) of various sorts we have looked at:

```
$ python timesorts.py
N: 2000
selection sort time: 0.1435
bubble sort time: 0.4378
python sort time: 0.0003
merge sort time: 0.0090
$ python timesorts.py
N: 4000
selection sort time: 0.5572
bubble sort time: 1.7164
python sort time: 0.0007
merge sort time: 0.0188
```

Notice the time for the merge sort does *not* quadruple like the selection
and bubble sort times. Also, python's built-in sort seems to be the best.
What algorithm does the built-in sort use???