Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Shortest Path/Recursion4/6/2009Opening Discussion●Do you have any questions about the quiz?●Minute Essay comments–Can we make a robot that does quantum mechanics?–Can we include plotting in a spreadsheet?Problem●We have two versions of minimum path.–You are driving on a long trip and want to find the the route from where you are to where you want to go where you will drive the fewest miles.–You are at a train station in one city and you want to get to another city. Each leg of the trip has a different cost and you want to find the cheapest route.How to solve it?●Let's break up into groups again for 10 minutes. I want you to discuss how you would solve this.●To help you out, I'll draw a picture on the board of a set of train stops and the connecting routes with costs on the routes.●You should figure out the cheapest route and tell me how you found it.●I'm going to add a little code to the Graph scenario to help us.Recursion●The method we are going to introduce to solve these problems (they are really the same problem), is recursion.●A recursive method is a method that calls itself.●Solve a problem by assuming you can solve the problem for other instances.●You have to have a base case.Simple Example●Each time you call a method, it gets its own little copy of local variables and parameters.●To help you understand recursion we can write two little methods that use recursion to give us the same behavior as loops.●What we will do to solve the problem would be hard to do with loops.Trying All Possibilities●The computer can solve this problem by trying every single route and keeping track of which one is cheapest.●With a little extra information stored at the stops, we can make it more like what a human does.●Let's write both of these.Minute Essay●Do you have any questions about what we talked about? What should be clarified on Wednesday for this
View Full Document