Last week we designed two algorithms that sort a list of n items: bubbleSort() and selectionSort(). We analyzed the algorithms and saw that each ran in O(n^2) time.
The file timeSort_sol.py contains working solutions to both sorting algorithms.
Open the file timeSort_soln.py. Use the timeSort() function to test the performance of each sorting algorithm on different sized inputs. Do the timing experiments confirm our analysis of the runtime? How do the runtimes of bubbleSort() and selectionSort() compare?
Any function that sometimes calls itself is known as a recursive function. In most cases, recursion can be considered an alternative to iteration (loops). Instead of defining a loop structure, recursion defines a problem as a smaller problem until it reaches an end point. There are three requirements for a successful recursive function:
Base case: each function must have one or more base cases where the function does not make a recursive call to itself. Instead, the problem has reached its smallest point, and we can begin returning back the small solutions.
Recursive case: the function makes one (or more) calls to itself. The call must use a different argument to the function (or else we keep making the same recursive call over and over again!). Typically, the problem gets 1 smaller.
All possible recursive calls must be guaranteed to hit a base case. If you miss one, your program is susceptible to an infinite recursion bug!
$ cd ~/cs21/inclass/w11-recursion/The printmessage.py program prints a given message n times. We have already seen how to solve this problem with a loop, but let's explore how we can solve it without a loop using recursion. To understand what is happening with recursion, it is helpful to draw a stack diagram. The key concept is that Python treats the recursive call the same as any function call - it places a new stack frame on top and begins executing the new function. The only difference is the function in this case has the same name.
$ cd ~/cs21/inclass/w11-recursion/We are going to write some iterative and recursive versions of the same function. Iterative versions use loops, recursive versions do not use loops, and instead contain calls to themselves but on a smaller problem. I have given you the code for an algorithm we have seen before - a for loop that sums all integers between 1 and n:
def iterativeSum(n):
total = 0
for i in range(n):
total = i+1
return totalTogether, we will write a recursive function that accomplishes the same task.
Recall the iterative version (using a loop) of factorial that takes a positive int value, n, and returns the product of the first n integers. Try writing a recursive version of the factorial function.
Open countdown.py. Explain the program to your neighbor. What is the recursive function doing? Can you identify the base vs recursive case? Are you sure that all recursive calls eventually hit the base case?
So far, the recursion exercises we've seen have been either simple tasks (printmessage.py, countdown.py) or numeric (computesum.py, factorial.py). Recursion is also useful when working with strings or lists.
Python provides some nice string functionality called slicing that can be particularly useful when working with recursion. Slicing lets you easily look at slices, or substrings of a function. The general syntax is mystr[i:j]. This gives the substring of mystr starting at index i and running up to but not including j.
$ python3
>>> hw = "hello world"
>>> hw[1]
'e'
>>> hw[7:10]
'orl'
>>> hw[0:5]
'hello'
>>> hw[6:]
'world'
>>> hw[:5]
'hello'You can also omit i or j. mystr[i:] gives you the substring starting at index i and running to the end of that string. mystr[:j] gives you the substring up to but not including the j-th character.
Note: slicing can also be used with lists e.g. if ls = [1,2,3,4,5], then ls[2:4] == [3,4].
A palindrome is a word or phrase that appears the same when read backwards or forwards. Examples include: "kayak" ,"taco cat", "Top spot", "no lemon, no melon", "able was I ere I saw Elba", and "may a moody baby doom a yam". In palindrome.py, write a recursive function isPalindrome that takes a string as input and returns True if the string is a valid palindrome, or false otherwise. Think first about base cases. When is your program free to not recurse? Then think about the general case. When do you know a string is not a palindrome?
For any recursive problem, think of these questions: