Unformatted text preview:

RECURSIONReference:• Roberts, Eric S., “Thinking Recursively”, John Wiley and Sons, 1986.An excellent, intuitive book.• Roberts, Eric S., “Thinking Recursively with Java”, John Wiley and Sons,2006.Presumably just as good as the older book.1Warning: beware of forward referencesThis set of slides discusses recursion, a way of programming (and thinking)that can be used in many areas of computing. In older versions of CSC148H/A48H, these slides were used late in the course, when suitable examplescould be drawn from many areas. Currently, we’re using it near the beginning,and some of those examples aren’t appropriate yet.They will be. For now, ignore referenc es to “tree”, “B STnodes”, and “iter-ators”. We’ll get to them.2The IdeaRecursion isn’t hard. You’v e been doing it your whole life.For example, how do you look up a word in a dictionary?// Look up w in d.look up word(Dictionary d, Word w) {find w in dread the definition of wfor each word v in the definitionif you don’t understand v, thenlook up word(d, v)put your understanding of the wordstogether to understand the definition}3Thinking RecursivelyImagine you have to solve one of the problems below, but you are very lazy.You can ask one or more equally lazy friends for help (so you can’t asksomeone to solve the whole problem — you have to do some work!)Problem: Calculate the value of 13!Problem: You have a two-pan balance and a pile of 32 quarters. One iscounterfeit and weighs slightly less than the others. Find it.How many weighings will it take?Problem: Given a set of characters, determine all possible permutations ofthat set.4To calculate the value of 13!• You can ask a friend what the value of 12! is, (and then later multiplythat by 13).• Your friend can ask another friend what 11! is ( and then multiply thatby 12).• . . .• Eventually, someone has to figure out the factorial of 1. This is so simplethat they can just answer “it’s 1”.• This answer is passed on to the person who needs to figure out 2!. Theycalculate 2 ∗ 1 = 2 and pass that answer on to the person who nee ds tofigure out 3!.• They calculate 3 ∗ 2 = 6, and pass it on to the pe rson who needs tofigure out 4!.• . . .• Eventually the first person has the value of 13!.5Divide and ConquerIn each case, we• Repeatedly break down a problem into subproblem(s) that– have the same structure as the original problem, but– are smaller or simpler to solve .• Eventually, the subproblem(s) are so simple that they can be solvedwithout further division.• The solution to the original problem consists of either:– the solution to the simplest subproblem, or– a combination of the solutions to the solved subproblems.Question: Identify how inorderPrint(BSTNode) follows this form.6The Definition of RecursionBecause a recursive solution to a problem requires that a “smaller” instanceof the same problem be solved, methods that are recursive call themselves.Definition: a recursive method is one that is called from within its own body,directly or indirectly.(E.g. indirectly: method A calls m ethod B which calls method A).7Suspicious?You may feel “suspicious” about re cursion, but don’t be: Think of the recur-sive call as no different from any other method call.We often examine non-recursive methods, assuming that any other methodsthey call will “do the right thing”.Similarly, for a recursive method, we c an consider what it will do assumingthat the recursive call will do the right thing.For example, for a non-empty tree , inorderPrint prints out the root’s valuein between printing out the lef t and right subtrees.This is correct, assuming that the two recursive calls do the right thing.8Tracing a recursive methodTrace a call to inorderPrint with a refere nce to the root of the following tree.Keep careful track of the call stack.55127 3960/** Print the tree rooted at t, in order. */private static void inorderPrint(BSTNode t) {if (t != null) {inorderPrint(t.left);System.out.println(t.key);inorderPrint(t.right);}}When you’re comfortable with re cursion, you’ll be able to write, understand,and debug recursive code without tracing the recursive calls. But don’t hesi-tate to trace if it helps you!9Writing a Recursive MethodProblem: Compute the height of a giv en tree.Get the basic strategy1. H ow can you reduce the problem to one or more simpler sub-problem s ofthe same form?10Flow of information2. What information dete rmines the subproblem (parameter(s)). What infor-mation do you want back about the subproblem (return value).3. Write the method header.4. Write a method specification that explains ex ac tly what it will do, in termsof the parameters. Include any necessary preconditions.11Base cases5. When is the answer so simple that we know it without recursing? Whatis the answer in these base case(s) (also called “degenerate”)? Don’t stopshort of the really simplest case!6. Describe the answer in the other case(s) in terms of the answer on smallerinputs.12Recursive steps7. Write c ode for the base case(s).8. Write code for the rec ursive case(s).9. Simplify if possible.13Conclusion10. Put it all together.14Recursing vs IteratingIterating has some similarity to rec ursing: each iteration of a loop does a bitof the work, and the remaining iterations finish the job.What’s missing is the “coming back” that we can do easily with recursion.An ExampleConsider the task of printing out the objects from an Iterator in reverseorder.When we get an object from the Iterator, it needs to be printed after theones we haven’t got yet. Recursion handles this easily:• if there’s a next object:– remembe r it– ask for the remaining objects to be printed in re verse order– print our remembered object15Write the method:Another Example: The Fibonacci SequenceThis Fibonacci seque nce is:1, 1, 2, 3, 5, 8, 13, 21, . . .Each number (except the first two) is the sum of the two numbers before it.We can implement a function to c alculate the nth Fibonacci number recur-sively . . .16Combinatorial Explosion/** Return the nth Fibonacci number f_n,* starting with f_1 = f_2 = 1.* Requires: n >= 1. */public static int fib(int n) {if (n > 2) {return fib(n - 1) + fib(n - 2);} else {return 1;}}Start tracing the calls for fib(6). Do you see any inefficiency?17Iterative FibonacciA natural (and faster) iterative version is:public static int fib(int n) {if (n == 1) {return 1;} // else n >= 2.int f1 = 1;int f2 =


View Full Document

Toronto CSC 148 - Recursion

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?