1More Recursion4-3-20062Opening Discussion■Do you have any questions about the quiz?■What did we talk about last class?■Do you have any questions about the assignment?3Maze Problems●Counting the number of paths is like shortest path only it adds up all answers and returns 1 when it gets to the end.●Shortest path can be optimized with different bread crumbs. The idea is that you can mark how many steps it took you to get someplace and never redo work if you get there on a longer path. Let's go ahead and write that code.4Bin Packing●Recursion is also extremely handy for solving problems where you want to “test all possible options”. The bin packing problem I gave you as extra credit for the first test is an example of this.●We need to test all possible ways of putting the items in the bins. We can do this with a function that tries all the items in the current bin and recurses with each attempt.5Divide and Conquer●Another common usage of recursive functions is in divide and conquer algorithms. In these, we repeatedly break a problem down into smaller pieces until we get to a point where we can solve it easily. We then combine the partial solutions to find a full solution.●Some extremely simple examples could be finding the sum of the elements of an array or the min of them.6Equation Parsing●Another fun application of divide and conquer is string parsing for things like equations. Here we break the problem up around the lowest priority operator and recursively parse smaller sections if the formula, then deal with then as we move back up the stack.●With just a little more work, this type of method can be turned into a very powerful tool.7Faster Sorts●Divide and Conquer can also be used to come up with faster sorting algorithms.●Mergesort - divide directly in two and recurse, then merge the two sorted halves. Does the work on the way back up.●Quicksort - pick a pivot, and move everything lower than the pivot to one side and everything higher to the other then recurse on the two sides. Does the work on the way down.8Object Oriented “Recursion”●In an object-oriented language we can find another type of recursive function. In this case we are looking at a method that calls the same method, but on a different object. The draw function in our semester example is like this.●Because the functions can be virtual, it isn’t always the same method that we are calling.9Coding■Let's play some more with the drawing program. Remember that you can look at everything we write during class. In fact, you probably should spend some time pulling these things down and looking at how they work.10Minute Essay■Write a function to do longest path on a maze. Note that this method can't be optimized.■The design for assignment #6 is due on
View Full Document