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.
If the length of A is 1, the sum of A is A's one element.
If the length of A is greater than 1, the sum of A is the first element of A plus the sum of the rest.
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.
If the list has one element, that element is its smallest.
If the list has more than one element, switch the first two elements if the first is less than the second and then find the smallest in the slice that goes from index 1 to the end of the 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.
If A has one element or no elements, the reverse of A is A.
If A has more than one element, the reverse of A is the final element of A concatenated with the reverse of the remainder of 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. )
If n is 1 or 2, then fib(n) is 1. (In English: the 1st and 2nd members of the Fibonacci sequence are both 1.)
If n is greater than 2, then fib(n) is the sum of fib(n - 1) and fib(n - 2). (In English: every member of the Fibonacci sequence after the second is the sum of the previous two members of that 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.
If m > n, switch their values. This ensures that m ≤ n.
If m evenly divides n, the GCF of m and n is m.
If m does not evenly divide n, the GCF of m and n equals the GCF of n modulo m and m. (Recall that n modulo m is the remainder when n is divided by m. Recall too that % is Python's remainder operator.)
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.)
24 < 32, and thus we don't need to switch the values of m and n.
24 does not evenly divide 32, so we say that the GCF of 24 and 32 equals the GCF of 24 and 32 mod 24 = 8.
We now find the GCF of 8 and 24. (This means that m is now 8 and n is now 24. Again, make sure to switch values if necessary so that m ≤ n.)
8 evenly divides 24, and thus the algorithm returns the value 8. 8 is the GCF of 24 and 32.
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):
If r is 1 or q equals r, pt_entry(q, r) is 1. (When r is 1, we're at the first element of a row and that's always 1. When q and r are equal, we're at the final element of a row and that's always 1 too.)
Otherwise pt_entry(q, r) = pt_entry(q - 1, r - 1) + pt_entry(q - 1, r). (The first is the element up and to the left of (q, r); the second is the element up and to the right.)
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:
Find the smallest factor of n that's greater than or equal to 2. Call this factor p.
If p equals n, n is prime and so the prime factorization of n is simply p.
If p is less than n, the prime factorization of n is p conjoined to the prime factorization of n // p.
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.
The smallest factor of 30 that's greater than or equal to 2 is 2. So the prime factorization of 30 is [2] conjoined to the prime factorization of 30 // 2 = 15.
The smallest factor of 15 greater than or equal to 2 is 3. So the prime factorization of 15 is [3] conjoined to prime factorization of 15 // 3 = 5.
The smallest factor of 5 greater than or equal to 2 is 5. So the prime factorization of 5 is [5]. This is the base case.
We can return to step 2 and say that the prime factorization of 15 = [3] + [5] = [3, 5].
Finally we can return to step 1 and say that the prime factorization of 30 = [2] + [3, 5] = [2, 3, 5].
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:
I suspect that you'll have multiple base cases. Base Case One: bracket purge an empty list. Base Case Two: bracket purge an object that is not a list.
In the Recursive Case, you'll know that the first element of the list is itself a non-empty list. What will you return? The bracket purge of the first element concatenated to the bracket purge of the remainder.
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.)
If U is empty, it's sorted. Thus if U is empty, qsort should return U.
If U isn't empty, choose an element of U. (It really doesn't matter which one. Choose at random. Choose the first. Choose the last. Just choose.) Call it pivot.
Remove pivot from U.
Create two lists, left and right. Left is all elements of U that are less than or equal to pivot. Right is all elements of U that are greater than pivot. When you build left and right, leave the order of elements unchanged.
We've broken U up into three parts - pivot, left and right. Left and right are themselves unsorted lists. So let's sort them! How? Quicksort of course. So here is our recursive call:
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.
If S is empty, return False. The empty list contains nothing and so doesn't contain t.
If S isn't empty, find the middle index of S. Call it m. (Note that I said "middle index", not "middle element". m is the position of the middle element, not the middle element itself.)
If S[m] is t, return True. Our item was found!
If S[m] isn't t, compare it to t. If t < S[m], run bchop on the left half of S; and if t > S[m], run bchop on the right half of S. (Yes, this is the recursive call. You slice S appropriately, and then send that slice to bchop.)
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.