''' 20211007 Robin Dawes ''' # Example 1 - recognizing palindromes def is_palindrome(s): ''' returns True if s is a palindrome, False if not s is expected to be a string (but a list can also be handled) ''' if len(s) <= 1: return True else: return (s[0] == s[-1]) and is_palindrome(s[1:-1]) def report_palindrome(s): ''' just dresses up the output a bit''' if is_palindrome(s): print(s,"is a palindrome\n") else: print(s,"is not a palindrome\n") print("\n") report_palindrome("radar") report_palindrome("baobab") # The version of is_palindrome just given is 100% correct, but it's not # as fast as it could be. The problem is that every time it recurses it # makes a slice of the string to pass to the parameter ... and making a slice # basically means making a copy. The longer the string is, the longer it takes # to make a copy. We can avoid making copies of the string by passing two more # parameters to the recursive function, which tell it which part of the string we # are currently working on. # This gives me an opportunity to introduce what I consider to be an important # principle in software design: functions that are intended to carry out some action # should make as few demands on the user as possible. (The rule is: never trust # the user - if you give them a chance to mess things up, they will. It's a version # of Murphy's Law.) # So if we want to have a function that someone (maybe even just ourselves) will # use to test a string to see if it is a palindrome, the function should just take the # string to be tested as a parameter. Don't require the user to provide other # information (length of the string, where to start, whatever. # To make this work we use what is sometimes called a "helper" function. This # is the function that the user calls. Its sole job is to figure out the values of the # extra parameters that the recursive function needs, and then to call the # recursive function to solve the problem. def is_palindrome_improved(s): ''' a helper function to set up and start the recursive function''' first = 0 last = len(s) -1 return is_palindrome_recursive_2(s, first, last) # or just "return is_palindrome_recursive_2(s, 0, len(s) - 1)" def is_palindrome_recursive_2(s, f, l): ''' determines if f is a palindrome without make time-consuming slices of s. Parameters f and l are respectively the first and last positions in the substring now being checked. ''' if l - f <= 0 : return True else: return (s[f] == s[l]) and is_palindrome_recursive_2(s, f+1, l-1) # These functions take advantage of something cauled "lazy evaluation" of Boolean # expressions. When Python (and other languages) encounters a complex Boolean # expression containing "ands" and "ors", it evaluates the expression from left to # right ... and it stops as soon as it knows what the answer is going to be. # An expression such as "(x == 2) and (y < 3)" is True if and only if both of the # conditions are True. So if we check the value of x and it turns out that x = 7, # then (x == 2) is False and that makes the whole expression False ... and we # know that without checking the truth of (y < 3) ! # This can be a significant time-saver if the expression is something like # "(x > 3) and very_slow_and_complex_function(n)" (where that function is # something that returns True or False). If the "x > 3" turns out to # be False, we don't need to call the very_slow_and complex_function. # Similarly, an "or" expression evaluates to True if either or both of its parts # evaluates to True. So in something like # "(x % 2 == 0) or another_very_slow_and_complex_function(n)", if "x % 2 == 0" # turns out to be True, we don't bother calling the function because we already # know that the whole expression is True. # It's called "lazy evaluation" because we only evaluate as much of a Boolean # expresson as we need to. def report_palindrome_2(s): if is_palindrome_improved(s): print(s,"is a palindrome and I found that out without slicing\n") else: print(s,"is not a palindrome and I found that out without slicing\n") report_palindrome_2("racecar") report_palindrome_2("sailboats") # Example 2 - Binary Search # Binary search is a fundamental algorithm that you will encounter over # and over. Whenever you learn a new programming language, a good # exercise is to write a binary search function in the new language. # The basic idea is that if we are searching a sorted list (or array) of numbers # to find a particular value, we can start by looking at the value in the middle # of the list. If it is the one we are looking for, hurray, we can stop. But if it # is too big, then all the numbers after it in the list are also too big (because the # list is sorted) so we can continue the search in just the first half of the list. # Similarly, if the value we look at in the middle is too small, we can continue # the search in just the second half of the list. In this way we repeatedly cut # the size of the search area in half until we either find the search target or # conclude that it is not there. # As before, we define a helper function to serve as the interface between # the user and the recursive function. The user supplies the list and the value # to be searched for. The helper function calls the recursive function with # appropriate parameters. def binary_search(a_list, x): ''' assumes a_list is in sorted order if x is in a_list, returns its position if x is not in a_list, returns -1 ''' return bin_search_rec(a_list, x, 0, len(a_list)-1) def bin_search_rec(the_list, x, first, last): ''' recursively searches the_list for x, looking at the values from the_list[first] up to the_list[last], inclusive. ''' if first > last: # Our recursive function MUST have a base case # In this case, we end the recursion when the range # of possible locations for x shrinks to 0 return -1 else: mid = (first + last) // 2 # find the middle position if the_list[mid] == x: # if x is found, return this position return mid elif the_list[mid] > x: # check to see if we go to the left ... return bin_search_rec(the_list, x, first, last-1) else: # ... or to the right return bin_search_rec(the_list, x, first+1, last) # testing the binary search function import random my_list = random.sample(range(10000), 10) # choose 10 random numbers # from this range print("\noriginal list", my_list) # the values are in random order target = my_list[0] # pick the first number chosen to be the one # to be searched for my_list.sort() print("\nsorted list", my_list) # who knows where that target value is now? print("\nsearching for", target) print("\n", target, "is now in position", binary_search(my_list, target)) # binary_search knows, that's who!