DOC PREVIEW
TRINITY CSCI 1321 - Recursion

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

TRINITY CSCI 1321 - Recursion

Documents in this Course
Recursion

Recursion

11 pages

Iterators

Iterators

10 pages

Actors

Actors

9 pages

Recursion

Recursion

15 pages

Threads

Threads

7 pages

Trees

Trees

11 pages

Load more
Download Recursion
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recursion and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recursion 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?