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
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
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
Now do find_max.
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]
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
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
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 - or maybe {1:1, 2:1}.
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.
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
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(r, c) designate the cth number in row r of Pascal's Triangle. For instance, pt_entry(2, 1) is 1, pt_entry(3, 2) is 2 and pt_entry(5, 3) is 6. Here's an algorithm to compute the value of pt_entry(r, c):
If r is 1 or q equals r, pt_entry(r, c) 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(r, c) is pt_entry(r - 1, c - 1) + pt_entry(r - 1, c). (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 may, if you wish, make both pt_entry and pt_row recursive. 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]
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 of its input that's greater than 1.
Test Cases:
>>> prime_factorization(2)
[2]
>>> prime_factorization(12)
[2, 2, 3]
>>> prime_factorization(30)
[2, 3, 5]
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]
I assume that you've done the Matrices project. If you haven't, at least read Section 1 of this. (If you're curious about the mathematical significance of determinants, you might begin here.)
In what follows, I'll assume that a matrix will be stored as a 2D list (that is, as a list of lists) in which the inner lists are rows of the matrix. For instance, the list [[1, 2], [3, 4]] will represent a 2-by-2 matrix whose first row is 1, 2 and whose second row is 3, 4. (Here and below I'll used indices as mathematicians use them; that is, the initial row has index 1 and the last row has index equal to the number of rows.)
The definition of determinant below makes use of the term "cofactor matrix". So let me define that first. A cofactor matrix C of a given matrix M is the result of the deletion of both a row and a column from M. For instance, if M = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] and we delete row 1 and column 2, we get the cofactor matrix [[4, 6], [7, 9]]. Note that, if matrix M has size n-by-n, then a cofactor matrix of M will have size (n-1)-by-(n-1); for instance, a cofactor matrix of a 5-by-5 matrix will be 4-by-4. I suggest that, before you attempt the determinant function, you first write a helper function named cofactor. It will take a matrix M, a row number r and a column number c, and return the matrix that results when row r and column c are removed from M. So, for instance, cofactor([[1, 2, 3], [4, 5, 6], [7, 8, 9]], 1, 2) should return the value [[4, 6], [7, 9]]. (cofactor need not be recursive.)
Now I'm ready to define determinant. My definition is recursive and thus is two part - the base case, and the recursive case. Let's agree to call the function you'll write det.
Base Case The determinant of the 2-by-2 matrix [[a, b], [c, d]] is a*d - b*c.
Recursive Case Let's say that matrix M has size n-by-n and that its first row has elements e1, e2, e3, ..., en. The determinant of M is:
e1 * det(cofactor(M, 1, 1)) - e2 * det(cofactor(M, 1, 2)) + e3 * det(cofactor(M, 1, 3)) - ...
Note that, in each term, the row and column deleted to produce the cofactor matrix are the row and column that contains the element of the row that begins that term. Note too that we flip the sign of each new term - begin positive, then negative, then positive, etc.
Test Cases:
>>> M = [[1, 2], [3, 5]]
>>> A = [[1, 2, 4], [3, -1, 7], [2, 5, 9]]
>>> det(A)
-1
>>> det(M)
-2
Back in the chapter on Selection, I built code for you that would return the total number of coin collections that total to a given value. I there assumed the coin values in use in the U.S. - 1 cent, 5 cents, 10 cents and 25 cents. I now what you to write a function that take a list of coin values and a total and returns the number of ways that a collection of coins of those values can give that total. Call it coin_counts. Assume that the coin values and the total to which the coins should sum are given in cents.
>>> coin_counts([1, 5, 10, 25, 50], 100)
292
>>> coin_counts([1, 5, 10, 25, 50], 500)
59868
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. If you're curious about this, a good place to begin is the Wikipedia article on Big O.) 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's our recursive call:
return qsort(left) + [pivot] + qsort(right)
Implement the Quicksort algorithm in Python. 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([])
[]
>>> qsort([1])
[1]
>>> qsort([3, 1, 2])
[1, 2, 3]
>>> qsort([3, 2, 3, 1, 2, 2, 1])
[1, 1, 2, 2, 2, 3, 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.)
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
I'll leave you with a final observation about just how efficient bchop is. Let's say that we had a list of 10,000 elements. How many times might we have to divide the list in half to determine whether it contains a particular value? Well, how many times can we divide 10,000 by 2 and still remain above 1? The answer is 13. That is, the greatest power of 2 that's less than 10000 is 13, for 2**13 = 8192 and 2**14 = 16384. That's really quite extraordinary! We need to examine at most 13 elements! (Ever heard of logarithms? We just took the log base 2 of 10,000 and rounded down.)
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. In the initial call to mqsort, we don't send values for left and right; but in the recursive calls - that is, when mqsort calls itself - values will be sent for both left and right.
We've done quite a bit of work with permutations. In Chapter 3, we computed the number of permutations of a list of length n. (That's n factorial.) In Chapter 7, we wrote code that handled permutations given in cycle notation. But as of yet, we haven't written a function that will take a list of items and produce all the permutations of that list. Let's do that now.
I propose that, before we attempt a recursive solution, we first ask ourselves how me might do this iteratively. Moreover, let's restrict ourselves to, let's say, lists of length 3. I know that's arbitrary, but, as we will see, it is nonetheless helpful to get a handle on the algorithm.
Let's say our list is L = ['a', 'b', 'c']. We wish to produce all 3! = 6 permutations of L. To do so, we'll build permutations and, after each is built, append it into a list I'll call P.
We'll have a for loop inside a for loop inside a for loop. The outer loop will choose from ['a', 'b', 'c']; that is, it will iterate through L, and in each iteration it will choose the next element. Thus the first time through the outer loop, it will choose 'a'. The next time through it will choose 'b'. The last time through it will choose 'c'.
When the outer loop makes a choice, it'll pop that choice from L, and then the middle loop will take over and do what the outer loop did. That is, it will iterate through the elements of L that remain and in each iteration choose the next element. The middle loop execute 3 times; the first time, L will be ['b', 'c'], the second time L will be ['a', 'c'] and the last time it will be ['a', 'b'].
Note that, before the middle loop gets its next value of L, the value that was popped out will have to be inserted back in. The outer loop will do that.
Let's consider the first iteration of the middle loop, when it gets ['b', 'c']. It first chooses 'b', pops that from L and then sends ['c'] along to the innermost loop. In its next iteration, it chooses 'c' and sends ['b'] to the innermost loop.
The innermost loop, since it only ever gets a list of length 1, will simply choose that one element.
If we put all this together, here are the permutations produced in the order they're produced:
['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']
Here's the code to do that. Please read carefully.
L = ['a', 'b', 'c'] # items to permute
P = [] # list into which permutations will be appended
for i in range(len(L)):
choiceOne = L[i]
L.pop(i)
for j in range(len(L)):
choiceTwo = L[j]
L.pop(j)
for k in range(len(L)):
choiceThree = L[k]
P.append([choiceOne, choiceTwo, choiceThree])
L.insert(j, choiceTwo) # place choiceTwo back in L
L.insert(i, choiceOne) # place choiceOne back in L
print(P)
Now let's move on to the general-purpose algorithm, the one that will produce all permutations of a list of any length. It will be recursive. It will have a for loop, as above we had for loops. But it will have only one for loop. How then will it be able to do what we did in the above program, where we had loops inside of loops? Well, we'll have the function call itself inside its loop! So the function will fire up again, and when it does another for loop will engage! That's how we'll get loops that loop!
So, write me a recursive function named permutations that will take a list L and produce a 2D list whose elements are the permutations of L.