Kĩ thuật lập trình - Recursion revisited

Recursion RevisitedCopyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.Java MethodsObject-Oriented Programmingand Data StructuresMaria Litvin ● Gary Litvin2nd AP edition  with GridWorld1Objectives:Take a fresh look at recursionLearn when to use recursion and when to stay away from itLearn to prove the correctness of recursive methodsGet ready for the Game of Hex lab 2Recursion BasicsA recursive method has a base case (or several base cases) and a recursive caseIn the base case, there are no recursive callsIn the recursive case, the method calls itself, but for a “smaller” taskRecursive calls must eventually converge to a base case, when recursion stops3Example 1 public String reverse (String s) { if (s.length() people, Person p1, Person p2, int n) { if (n == 1) { return p1.knows (p2); } else { for (Person p : people) { if (p1.knows (p) && degreeOfSeparation (people, p, p2, n-1)) return true; } return false; } }Base caseRecursive casep1p2p7When to Use RecursionRecursion is especially useful for handling nested structures and branching processes8Example 5 public void traverse (TreeNode root) { if (root != null) { display (root.getValue ( )); traverse (root.getLeft ( )); traverse (root.getRight ( )); } }123Recursive case1239Example 6 public void permutations (StringBuffer str, int n) { if (n = 0; i--) r += s.charAt (i); return r; }12Not Easy Without Recursion public void traverse (TreeNode root) { if (root != null) { display (root.getValue ()); traverse (root.getLeft ()); traverse (root.getRight ()); } }Rule of thumb: use recursion when the process is branching, that is, when the method is called recursively more than once or within a loopNeed your own stack to do this without recursion13Very Inefficient Recursive Code public long fibonacci (int n) { if (n 2) { next = f1 + f2; f1 = f2; f2 = next; n--; } return f2; }fibonacci (100) takes 50 years to runfibonacci (100) takes a few microseconds to run14Recursion and Math InductionRecursive methods are hard to trace in a conventional way.A recursive method can be proven correct using math induction.Other properties of a recursive method (running time, required space, etc.) can be obtained by using math induction.15Math Induction BasicsYou have a sequence of statements P1, P2, P3, ... Pn-1 , Pn , ...Suppose P1 is true (“base case”).Suppose you can prove that for any n > 1, if P1, ... Pn-1 are all true then Pn must be true, too.Then you can conclude (“by math induction”) that Pn is true for any n  1It is often possible to prove that if Pn-1 is true then Pn is also true.16Math Induction Example:Prove that for any n  1 1 + 2 + 4 + ... + 2n = 2n+1 - 1Proof:1. If n = 1 then 1 + 2 = 22 - 12. Suppose (induction hypothesis) 1 + 2 + 4 + ... + 2n-1 = 2n - 1 Then 1 + 2 + 4 + ... + 2n = (1 + 2 + 4 + ... 2n-1) + 2n = (2n - 1) + 2n = 2·2n - 1 = 2n+1 - 1By math induction, the equality is true for any n  1, q.e.d.17Math Induction and Recursion public String reverse (String s) { if (s.length( ) 1Move the top n-1 disks to a spare peg (recursive step).Move the bottom disk to the desired peg.Move all n-1 disks from the spare to the desired peg (recursive step). 21The Game of HexTwo players take turns placing a stone of their colorObjective: connect your pair of the opposite sides of the board with stones of your color22Each cell has six “logical” neighborsThe Game of Hex (cont’d)Computer representation of the board in a 2-D array23The Game of Hex (cont’d)To detect a win, determine whether any “blob” (connected group of stones) touches the opposite sides24The Game of Hex (cont’d)This kind of task falls into the category of “area fill” tasks25Review:What is recursion?How is recursion implemented in a computer?What kinds of applications especially benefit from recursion?Give an example of a task that can be programmed recursively and also, as easily, with iterations.26Review (cont’d):Give an example of a task that would be rather hard to program without recursion. Give an example of a method that is too slow in a naïve recursive implementation.What mathematical tool is very useful for understanding recursive methods and proving them correct?27Review (cont’d):What is the number of moves necessary to solve the Tower of Hanoi puzzle with 1, 2, 3, ..., n disks? How would you prove your hypothesis?Can you come up with an idea for a recursive algorithm for “area fill”?28