1Recursion and inductionWe teach these early, instead of new object-oriented ideas, so that those who are new toJava can have a chance to catch up on theobject-oriented ideas from CS100.Readings:Weiss, Chapter 7, page 231-249.CS211 power point slides for recursionDefinition:Recursion: If you get the point, stop;otherwise, see Recursion.Infinite recursion: See Infiniterecursion.2RecursionRecursive definition: A definition that isdefined in terms of itself.Recursive method: a method that calls itself(directly or indirectly).Recursion is often a good alternative to itera-tion (loops). Its an important programmingtool. Functional languages have no loops --only recursion.Homework: See handout.3Recursive definitions in mathematicsFactorial:!0 = 1 base case!n = n * !(n-1) for n > 0 recursive caseThus, !3 = 3 * !2 = 3 * 2 * !1 = 3 * 2 * 1 * !0 = 3 * 2 * 1 * 1 (= 6)Fibonacci sequence:Fib0 = 0 base caseFib1 = 1 base caseFibn = Fibn-1 + Fibn-2 for n > 1 recursive case0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …4Turn recursive definition into recursive functionFactorial:!0 = 1 base case!n = n * !(n-1) for n > 0 recursive caseThus, !3 = 3 * !2 = 3 * 2 * !1 = 3 * 2 * 1 * !0 = 3 * 2 * 1 * 1 (= 6)// = !n (for n>=0)public static int fact(int n) { if (n == 0) {return 1; base case } // {n > 0} an assertion return n * fact(n-1); recursive case} (a recursive call)Later, we explain why this works.note the precise specification5Turn recursive definition into recursive functionFibonacci sequence:Fib0 = 0 base caseFib1 = 1 base caseFibn = Fibn-1 + Fibn-2 for n > 1 recursive case0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …// = Fibonacci number n (for n >= 0)public static int Fib(int n) { if (n <= 1) { can handle bothreturn n; base cases together } // {n > 0} an assertion return Fib(n-1) + Fib(n-2); recursive case} (two recursive calls)Later, we explain why this works.note the precise specification6Two issues incoming to grips with recursion1. How are recursive calls executed?2. How do we understand a recursivemethod and how do we write-create arecursive method?We will handle both issues carefully. But forproper use of recursion they must be keptseparate.We DON’T try to understand a recursivemethod by executing its recursive calls!7Understanding a recursive methodMEMORIZE THE FOLLOWINGStep 0: HAVE A PRECISE SPECIFICATION.Step 1: Check correctness of the base case.Step 2: Check that recursive-call arguments arein some way smaller than the parameters, so thatrecursive calls make progress toward termination(the base case).Step 3: Check correctness of the recursive case.When analyzing recursive calls, use thespecification of the method to understand them.Weiss doesn’t have step 0 and adds point 4,which has nothing to do with “understanding”.4: Don’t duplicate work by solving someinstance in two places.8Understanding a recursive methodFactorial:!0 = 1 base case!n = n * !(n-1) for n > 0 recursive caseStep 1: HAVE A PRECISE SPECIFICATION// = !n (for n>=0)public static int fact(int n) { if (n == 0) {return 1; base case } // {n > 0} return n * fact(n-1); recursive case} (a recursive call)Step 2: Check the base case.When n = 0, 1 is returned, which is 0!. So thebase case is handled correctly.9Understanding a recursive functionFactorial:!0 = 1 base case!n = n * !(n-1) for n > 0 recursive caseStep 3: Recursive calls make progress towardtermination.// = !n (for n>=0)public static int fact(int n) { if (n == 0) {return 1; } // {n > 0} return n * fact(n-1); recursive case}argument n-1 is smaller thanparameter n, so there is progresstoward reaching base case 0parameter nargument n-110Understanding a recursive functionFactorial:!0 = 1 base case!n = n * !(n-1) for n > 0 recursive caseStep 4: Check correctness of recursive case; usethe method spec to understand recursive calls.// = !n (for n>=0)public static int fact(int n) { if (n == 0) {{ return 1; } return n * fact(n-1); recursive case}In the recursive case, the value returned is n * fact(n -1).Using the specification for method fact, we see thisis equivalent ton * !(n -1).That’s the definition of !n, so the recursive case iscorrect.11Creating recursive methodsUse the same steps that were involved inunderstanding a recursive method.• Be sure to SPECIFY THE METHOD PRECISELY.• Handle the base case first.• In dealing with the non-base cases, thinkabout how you can express the task in termsof a similar but smaller task.12Creating a recursive methodTask: Write a method that removes blanksfrom a String.0. Specification:// = s but with its blanks removedpublic static String deblank(String s)1. Base case: the smallest String is “”. if (s.length == 0)return s;2. Other cases: String s has at least 1 character.If it’s blank, return s[1..] but with its blanksremoved. If it’s not blank, return s[0] + (s[1..] but with its blanks removed)Notation: s[i] is shorthand for s.charAt[i].s[i..] is shorthand for s.substring(i).precise specification!13Creating a recursive method// = s but with its blanks removedpublic static String deblank(String s) { if (s.length == 0)return s; // {s is not empty} if (s[0] is a blank)return s[1..] with its blanks removed // {s is not empty and s[0] is not a blank} return s[0] + (s[1..] with its blanks removed);}The tasks given by the two English, blueexpressions are similar to the task fulfilled bythis function, but on a smaller String! !!!Rewriteeach as deblank(s[1..]) .Notation: s[i] is shorthand for s.charAt[i].s[i..] is shorthand for s.substring(i).14Creating a recursive method// = s but with its blanks removedpublic static String deblank(String s) { if (s.length == 0)return s; // {s is not empty} if (s.charAt(0) is a blank)return deblank(s.substring(1)); // {s is not empty and s[0] is not a blank} return s.charAt(0) + deblank(s.substring(1));}Check the four points:0. Precise specification?1. Base case: correct?2. Recursive case: progress toward termination?3. Recursive case: correct?15Creating a recursive methodTask: Write a method that tests whether aString is a palindrome (reads the samebackwards and forward).E.g. palindromes: noon, eve, ee, o, “” nonpalindromes: adam, no0. Specification:// = “s is a palindrome”public static boolean isPal(String s)1. Base case: the smallest String is “”. A stringconsisting of 0 or 1 letters is a palindrome. if (s.length() <= 1)return true; // { s has at least two
View Full Document
Unlocking...