Algorithms For Dummies. John Paul Mueller
alt="Remember"/> Note the difference. Instead of checking the ending condition, this version checks the continuation condition. As long as
n is greater than 1, the code will continue to make recursive calls. Even though this code is shorter than the previous version, it's also less clear because now you must think about what condition will end the recursion.
Eliminating tail call recursion
Many forms of recursion rely on a tail call. In fact, the first example in the previous section does. A tail call occurs any time the recursion makes a call to the function as the last thing before it returns. In the previous section, the line return n * factorial(n-1) is the tail call.
Tail calls aren’t necessarily bad, and they represent the manner in which most people write recursive routines. However, using a tail call forces Python to keep track of the individual call values until the recursion rewinds. Each call consumes memory. At some point, the system will run out of memory and the call will fail, causing your algorithm to fail as well. Given the complexity and huge datasets used by some algorithms today, tail calls can cause considerable woe to anyone using them.
With a little fancy programming, you can potentially eliminate tail calls from your recursive routines. You can find a host of truly amazing techniques online, such as the use of a trampoline, as explained at https://blog.moertel.com/posts/2013-06-12-recursion-to-iteration-4-trampolines.html. (Mind you, this isn’t the sort of trampoline you jump on at home!) However, the simplest approach to take when you want to eliminate recursion is to create an iterative alternative that performs the same task. For example, here is a factorial() function that uses iteration instead of recursion to eliminate the potential for memory issues:
def factorial(n): print("factorial called with n = ", str(n)) result = 1 while n > 1: result = result * n n = n - 1 print("Current value of n is ", str(n)) print("Ending condition met.") return result print(factorial(5))
The output looks very similar to before:
factorial called with n = 5Current value of n is 4Current value of n is 3Current value of n is 2Current value of n is 1Ending condition met.120
The basic flow of this function is the same as the recursive function. A while loop replaces the recursive call, but you still need to check for the same condition and continue looping until the data meets the condition. The result is the same. However, replacing recursion with iteration is nontrivial in some cases, as explored in the example at https://blog.moertel.com/posts/2013-06-03-recursion-to-iteration-3.html.
Performing Tasks More Quickly
Obviously, getting tasks done as quickly as possible is always ideal. However, you always need to carefully weigh the techniques you use to achieve this efficiency. Trading a little memory to perform a task faster is great as long as you have the memory to spare. Later chapters in the book explore all sorts of ways to perform tasks faster, but you can try some essential techniques no matter what sort of algorithm you're working with at any given time. The following sections explore some of these techniques.
Considering divide and conquer
Some problems look overwhelming when you start them. Take, for example, writing a book. If you consider the entire book, writing it is an overwhelming task. However, if you break the book into chapters and consider just one chapter, the problem seems a little more doable. Of course, an entire chapter can seem a bit daunting, too, so you break the task down into first-level headings, which seems even more doable, but still not quite doable enough. The first-level headings could contain second-level headings and so on until you have broken down the problem of writing about a topic into short articles as much as you can. This is how divide and conquer works. You break a problem down into smaller problems until you find a problem that you can solve without too much trouble.
Computers can use the divide-and-conquer approach as well. Trying to solve a huge problem with an enormous dataset could take days — assuming that the task is even doable. However, by breaking the big problem down into smaller pieces, you can solve the problem much faster and with fewer resources. For example, when searching for an entry in a database, searching the entire database isn’t necessary if you use a sorted database. Say that you’re looking for the word Hello in the database. You can begin by splitting the database in half (letters A through M and letters N through Z). The letter H in Hello is less than M in the alphabet, so you look at the first half of the database rather than the second. Splitting the remaining half again (letters A through G and letters H through M), you now find that you need the second half of the remainder, which is now only a quarter of the database. Further splits eventually help you find precisely what you want by searching only a small fraction of the entire database. You call this search approach a binary search. The problem becomes one of following these steps:
1 Split the content in question in half.
2 Compare the keys for the content with the search term.
3 Choose the half that contains the key.
4 Repeat Steps 1 through 3 until you find the key.
def search(searchList, key): mid = int(len(searchList) / 2) print("Searching midpoint at ", str(searchList[mid])) if mid == 0: print("Key Not Found!") return key elif key == searchList[mid]: print("Key Found!") return searchList[mid] elif key > searchList[mid]: print("searchList now contains ", searchList[mid:len(searchList)]) search(searchList[mid:len(searchList)], key) else: print("searchList now contains ", searchList[0:mid]) search(searchList[0:mid], key) aList = list(range(1, 21))search(aList, 5)
When you run this code, you see this output:
Searching midpoint at 11searchList now contains [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Searching midpoint at 6searchList now contains [1, 2, 3, 4, 5]Searching midpoint at 3searchList now contains [3, 4, 5]Searching midpoint at 4searchList now contains [4, 5]Searching midpoint at 5Key Found!
This recursive approach to the binary search begins with aList containing the numbers 1 through 20. It searches for a value of 5 in aList. Each iteration of the recursion begins by looking for the list's midpoint, mid, and then using that midpoint to determine the next step. When the key matches the midpoint, the value is found in the list and the recursion ends.
key is greater than the midpoint value of the existing list, searchList[mid], the code calls search again with just the right side of the remaining list. In other words, every call to search uses just half the list found in the previous call.