Chp 8 Functions

Instructions

Write each recursive function described below. As always, I suggest that you first go through a create a skeleton function for each. Like this:

def sum_of():

    pass

def product_of():

    pass

Etc.

When done with the skeleton functions, paste in the unit test.

Addition

What's the sum of a list of integers that's one long? Just that integer of course. For example, the sum of the list [12] is just 12. What's the sum of a list of integers that’s more than one long? The first integer plus the sum of the rest of the list. For example, sum[1, 3, 12, 15] = 1 + sum[3, 12, 15].

This suggests a recursive algorithm for addition. Assume that A is a nonempty list of integers.

Write a function that implements this recursive algorithm. Name it sum_of. The function should take a list of numbers and return their sum.

Test Cases:

>>> sum_of([12])

12

>>> sum_of([1, 3, 12, 15])

31

Multiplication

Implement multiplication as a recursive algorithm. Bundle that algorithm up in a function named product_of. The function should take a list of numbers and return their product.

Test Cases:

>>> product_of([12])

12

>>> product_of([1, 3, 12])

36

Minimum Element

Here's a curious little algorithm to find the smallest element in a list.

The algorithm is recursive, since in step two we are asked to again find the smallest element of a list. But note that, when asked to find the smallest element of a list in step two, the list is smaller than it was before. Thus we're guaranteed that the algorithm will finally terminate.

Implement the algorithm above in a recursive function called find_min. This function should take a list of numbers and return the minimum element of that list.

Test Cases:

>>> find_min([12])

12

>>> find_min([15, 3, 1, 12])

1

Maximum Element

Now do find_max.

List Reverse

Here's a clever little recursive algorithm that reverses a list. Assume that the list's name is A.

 Here's an example. (The function name is reverse.)

reverse([1, 2, 3]) →

[3] + reverse([1, 2]) →

[3] + [2] + reverse([1]) →

[3] + [2] + [1] →

[3, 2, 1] 

Implement this recursive algorithm in Python. This function should take a  list and return a list.

Test Cases:

>>> reverse([12])

[12]

>>> reverse([1, 3, 12, 15])

[15, 12, 3, 1]

Triangular Numbers

If n is a positive integer, the nth triangular number is the sum first n positive integers. For example, the 5th triangular number is 1 + 2 + 3 + 4 + 5 = 15.

Write a recursive function named tri_num that takes a positive integer n and returns the nth triangular number. (It might help if I use a name for this function that I've heard student use. That name is "sumtorial".)

Test Cases:

>>> tri_num(1)

1

>>> tri_num(3)

6

>>> tri_num(5)

15

The Fibonacci Sequence

Here's the classic recursive algorithm for the Fibonacci sequence. (fib(n) designates the nth element of the Fibonacci sequence. )

Implement this recursive algorithm in Python. Call your recursive function fib. It should take a positive integer n and return the nth Fibonacci number.

Test Cases:

>>> fib(1)

1

>>> fib(2)

1

>>> fib(3)

2

>>> fib(12)

144

Fast Fib

If you wrote the previous function in the simple and obvious way (probably four or so lines of code), it will be intolerably slow for inputs as small as the upper 30's.  Let's think for a moment about why that is. I assume that your base case was something like this:

if n == 1 or n == 2:

    return 1

So, whenever the function does not recursively call itself, it returns 1; and this means that the computation of fib(n) is achieved by the repeated addition of 1. Thus, since fib(10) = 55, fib(10) is computed by the sum 1 + 1 + ... + 1, where the number of 1's is 55; and fib(30) is computed by a sum of 1's that contains 832040 1's, since fib(30) = 832040,

Can we do better? Well, in one way, of course we can. We can write an iterative algorithm, not a recursive one. That's fast. (You did this in Chapter 3, the chapter on iteration.) But we can keep the algorithm recursive and still do much better.

How? Memoize. (No, I didn't leave out the 'r'. That's how it's spelled. Google it if you want to read more.) What does that mean? Simply put, it means to store values of the function so that later those values can be used instead of recomputed. How does this help? Well, consider the computation of fib(5). The recursive algorithm tells us that this is fib(3) + fib(4). (Notice that I placed the smaller of the two arguments on the left. This was deliberate. Python will fully evaluate fib(3) before it returns to find fib(4).) So we must then first go off in search of fib(3), which of course is fib(1) + fib(2); and that, we know, is simply 1 + 1. Now, let's say that we stored the value of fib(3). So, when we return back to fib(4), which is fib(3) + fib(2), instead of compute fib(3) again from scratch, we can just pull the stored value of fib(3). That's so much faster.

The larger the input grows, the more work we save if we memoize. For instance, if the input is 30, the slow recursive algorithm calls itself 1664079 times; and if we use the fast one, the one that memoizes, it calls itself 57 times. That's a huge difference!

What I want you to do, then, is to rewrite the slow fib function so that it now memoizes. How? Well, computed values will have to be stored. A dictionary seems like a good choice here; and the first line of the function will have to be rewritten so that it now takes as input that dictionary. A problem of course is that that dictionary must have an initial value. ({1:1, 2:1} seems like a good choice.) But we cannot make the initialization a line of code in the function, for if we do it will always be reset and so can't store values of the fib function that have been already computed. How do we get around that? Set a default value for a parameter. In particular, have a parameter for the dictionary that will store already-computed values, and makes its default value the empty dictionary.

Call your rewrite fast_fib.

>>> fast_fib(100)

354224848179261915075

>>> fast_fib(500)

139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

>>> fast_fib(1000)

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

All of these were computed in well under a second.

The Greatest Common Factor

Here's a bad way to find the greatest common factor of a pair of numbers: generate a list of all numbers that are factors of both and then select the largest from that list.

Euclid’s Algorithm is a better way. A much better way. Here's how it works. Let's say that we have two positive integers, call them m and n, and we wish to find their GCF.

This algorithm is recursive.

 An example will help. Let's say that we wish to find the GCF of 24 and 32. (We thus assign 24 to m and 32 to n.)

Implement the Euclidean algorithm recursively in a function named gcf. This function should take a pair of positive integers and should return their GCF.

Test Cases:

>>> gcf(1, 1)

1

>>> gcf(24, 32)

8

>>> gcf(17, 37)

1

Pascal's Triangle

Google "Pascal's Triangle". Teach yourself how to construct it.

Write me a function that generates the nth row of Pascal's triangle. Call it pt_row. It should take a positive integer n. It should return the nth row of Pascal's Triangle (in the form of a list).

Surely you suspect that you should make use of recursion. You should. How?

Let pt_entry(q, r) designate the rth number in row q of Pascal's Triangle. For instance, pt_entry(2, 1) = 1, pt_entry(3, 2) = 2 and pt_entry(5, 3) = 6. Here's an algorithm to compute the value of pt_entry(q, r):

So I suggest you define two functions, pt_entry and pt_row. The second will call the first. Repeatedly.

You make, if you wish, make both pt_entry and pt_row. You may also make only pt_entry recursive; if you do, you'll have a for loop in pt_row. How might you make pt_row recursive? I suggest that the function have two parameters, the second of which has a default value. Like this: def pt_row (n, i = 1).  When you call pt_row from outside the function, you do so with a single argument, which of course becomes the value of n; and the value of i will default to 1.  But when pt_row calls itself, it will do so with two arguments, and the second will override the default value of i.

Test Cases:

>>> pt_row(1)

[1]

>>> pt_row(2)

[1, 1]

>>> pt_row(3)

[1, 2, 1]

>>> pt_row(6)

[1, 5, 10, 10, 5, 1]

Prime Factorization

Let's say that we wish to produce the prime factorization of a positive integer n. (Assume that it's 2 or greater.) Here's a way:

In the final clause, we're asked to find the prime factorization of another number. Thus the definition is recursive.

Let's work through this algorithm by hand. We'll find the prime factorization of 30.

Implement this recursive algorithm in a function named prime_factorization. This function should take a positive integer greater than or equal to 2 and should return its prime factorization in list form.  I expect you'll want to write a helper function named first_factor. It will deliver the first factor that's greater than 1.

Test Cases:

>>> prime_factorization(2)

[2]

>>> prime_factorization(12)

[2, 2, 3]

>>> prime_factorization(30)

[2, 3, 5]

Bracket Purge

Syntactically, to bracket purge a list is to remove all of the brackets except for the first and last. Below are examples of lists that have been bracket purged.

[1, 2] → [1, 2]

[[1]] → [1]

[1, [1, 2]] → [1, 1, 2]

[[ ], [[1, 2]], 3, [4, [ 5, 6]]] → [1, 2, 3, 4, 5, 6]

Write a recursive function named bracket_purge that takes a list and returns that list with all but the outermost brackets purged. Points to consider:

Here's a bit of perfectly good Python syntax: type(var_name) is not list. This is a Boolean expression. Its value is True if the object named by var_name is not a list; its value is False if the object name by var_name is a list.

Test Cases:

>>> bracket_purge([])

[]

>>> bracket_purge([[[]]])

[]

>>> bracket_purge([1])

[1]

>>> bracket_purge([1, 2, 3])

[1, 2, 3]

>>> bracket_purge([[1, 2], 3])

[1, 2, 3]

>>> bracket_purge([[1, 2], [3, [[[4]]]]])

[1, 2, 3, 4]

Quicksort

You implemented two sort algorithms in the Lists and Tuples chapter; they were Bubble Sort and Selection Sort. Neither is efficient. Quicksort is much better.  (If you take another CS class, you'll likely study in detail ways in which to measure algorithm efficiency.) I generated a list of 10000 random integers. Bubble sort took almost a minute to sort it. Quicksort took under a second.

How does Quicksort work? Here's the idea. (Assume that "U" is the name of the list we wish to sort and that "qsort" is the name of our recursive function.)

return qsort(left) + [pivot] + qsort(right)

Implement the Quicksort algorithm in Python. Place it within a function name qsort. That function should take a list of numbers and should return that list sorted from least to greatest.

Note that each recursive call to qsort will take use closer to the base case, since both left and right must be smaller U.

I suggest you also create a second, helper function, named perhaps split. If you send it your list and your pivot, it will return left and right. (I never told you to not create functions other than the ones I've named for you. Indeed I told you that in many cases, you probably should create one or more non-mandatory helper functions. Remember: a function should ideally carry out one and only one task, and thus if you realize that you've written a multitask function, you should probably break it up into multiple functions.)

Test Cases:

>>> qsort([1])

[1]

>>> qsort([3, 1, 2])

[1, 2, 3]

(The algorithm sketched above is memory extravagant. It creates lots of new lists. In a moment, I'll have you rewrite qsort in such a way that no new lists are created.)

Binary Chop

Sort and search are best of friends. Why sort a list? So we can search it more efficiently! Have a list that you'll search many times? Sort it first!

We now have an efficient sort algorithm. We call it Quick Sort, and quick it is. Now let's have an efficient search algorithm. We'll use one called "Binary Chop". (Actually, that's not the most common name. But I can't resist the temptation to call it "chop".)

The idea is simple. Go to the middle of the sorted list. If your item is there, you're done. If not, then since the list is sorted, you'll know where to look. If your item is less, search the left; if greater, search the right. Continue on until either you find your item or you run out of halves to search.

This is clearly recursive. How do you search? Look in the middle, and if not there search half the list. Now look in the middle of the half. Is it there? Yes? Done! If not, search a half of a half. Etc. To search, you must search; and each new search is a smaller search. The very model of recursion!

Let's get a little closer to actual code. S is the sorted list, t is the item for which we search, bchop is the search function.

Test Cases:

>>> bchop([], 1)

False

>>> bchop([1], 1)

True

>>> bchop([1, 2, 4], 3)

False

Quicksort In Place (Extra Credit)

The Quicksort algorithm described above is not a mutator. It leaves the input list as it was and returns a new list with the elements of the old sorted. Let's Quicksort again, but this time let's make it a mutator. The new version will move elements about in the input list until it's sorted.

How? Well, we'll still have a pivot. But now we'll move elements of the list until the pivot is greater than all elements on its left and less than or equal to all elements on its right; and after we've done this, we'll call Quicksort twice, once for the portion of the list before the pivot and once for the portion after. This means that when we call the new Quicksort function, we'll have to send two indices along as well; these will be the indices of the leftmost and rightmost elements of that portion of the list we wish to sort.

Call this new Quicksort mqsort. The "m" is for "mutator".

>>> L = [3, -2, 5, 1, 0, 6, 4, 7, -3]

>>> mqsort(L)

>>> L

[-3, -2, 0, 1, 3, 4, 5, 6, 7]

Perhaps you're puzzled. I said that when we call mqsort, we need to send not only a list but a pair of indices as well.  But in the code sample above, mqsort was sent simply the list L. What's up with this? I'll answer with a few lines of my code:

def mqsort(A, left = None, right = None):

    if left is None:

        left, right = 0, len(A) - 1

(This is an example of default parameter values, mentioned above in the fast_fib function.) left and right are indices. I gave them default values, None for both.