RECURSION

RECURSION
LexiWills Profile Pic
LexiWills,United Kingdom,Professional
Published Date:31-07-2017
Your Website URL(Optional)
Comment
RECURSION Lecture 6 CS2110 – Fall 2013 Overview references to sections in text 2 ¨  Note: We’ve covered everything in JavaSummary.pptx ¨  What is recursion? 7.1-7.39 slide 1-7 ¨  Base case 7.1-7.10 slide 13 ¨  How Java stack frames work 7.8-7.10 slide 28-32 Homework. Copy our “sum the digits” method but comment out the base case. Now run it: what happens in Eclipse? Now restore the base case. Use Eclipse in debug mode and put a break statement on the “return” of the base case. Examine the stack and look at arguments to each level of the recursive call. Recursion 3 Arises in two forms in computer science ¤  Recursion as a mathematical tool for defining a function in terms of itself in a simpler case ¤  Recursion as a programming tool. You’ve seen this previously but we’ll take it to mind-bending extremes (by the end of the class it will seem easy) Mathematical induction is used to prove that a recursive function works correctly. This requires a good, precise function specification. See this in a later lecture. Recursion as a math technique 4 Broadly, recursion is a powerful technique for defining functions, sets, and programs A few recursively-defined functions and programs ¤  factorial ¤  combinations ¤  exponentiation (raising to an integer power) Some recursively-defined sets ¤  grammars ¤  expressions ¤  data structures (lists, trees, ...) Example: Sum the digits in a number 5 / return sum of digits in n. Precondition: n = 0 / public static int sum(int n) sum calls itself if (n 10) return n; // n has at least two digits // return first digit + sum of rest return n%10 + sum(n/10); ¨  E.g. sum(87012) = 2+(1+(0+(7+8))) = 18 Example: Is a string a palindrome? 6 / = "s is a palindrome" / public static boolean isPal(String s) if (s.length() = 1) Substring from return true; s1 to sn-1 // s has at least 2 chars int n= s.length()-1; return s.charAt(0) == s.charAt(n) && isPal(s.substring(1, n)); r a c e c a r a c e c a ¨  isPal(“racecar”) = true c e c ¨  isPal(“pumpkin”) = false e Example: Count the e’s in a string 7 / = number of times c occurs in s / public static int countEm(char c, String s) if (s.length() == 0) return 0; Substring s1.., i.e. s1, …, // s has at least 1 character s(s.length()-1) if (s.charAt(0) = c) return countEm(c, s.substring(1)); // first character of s is c return 1 + countEm (c, s.substring(1)); ¨  countEm(‘e’, “it is easy to see that this has many e’s”) = 4 ¨  countEm(‘e’, “Mississippi”) = 0 Example: The Factorial Function (n) 8 Define n = n·∙(n-1)·∙(n-2)·∙·∙·∙3·∙2·∙1 read: “n factorial” E.g. 3 = 3·∙2·∙1 = 6 Looking at definition, can see that n = n (n-1) By convention, 0 = 1 The function int → int that gives n on input n is called the factorial function A Recursive Program 9 0 = 1 n = n·(n-1), n 0 / = n. Precondition: n = 0 / static int fact(int n) if (n = = 0) return 1; // n 0 return nfact(n-1); General Approach to Writing Recursive Functions 10 1.  Find base case(s) – small values of n for which you can just write down the solution (e.g. 0 = 1) 2.  Try to find a parameter, say n, such that the solution for n can be obtained by combining solutions to the same problem using smaller values of n (e.g. (n-1) in our factorial example) 3.  Verify that, for any valid value of n, applying the reduction of step 1 repeatedly will ultimately hit one of the base cases Example: Tower of Hanoi Legend has it that there were three diamond needles set into the floor of the temple of Brahma in Hanoi. Stacked upon the leftmost needle were 64 golden disks, each a different size, stacked in concentric order: A Legend The priests were to transfer the disks from the first needle to the second needle, using the third as necessary. But they could only move one disk at a time, and could never put a larger disk on top of a smaller one. When they completed this task, the world would end To Illustrate For simplicity, suppose there were just 3 disks, and we’ll refer to the three needles as A, B, and C... Since we can only move one disk at a time, we move the top disk from A to B. Example For simplicity, suppose there were just 3 disks, and we’ll refer to the three needles as A, B, and C... We then move the top disk from A to C. Example (Ct’d) For simplicity, suppose there were just 3 disks, and we’ll refer to the three needles as A, B, and C... We then move the top disk from B to C. Example (Ct’d) For simplicity, suppose there were just 3 disks, and we’ll refer to the three needles as A, B, and C... We then move the top disk from A to B. Example (Ct’d) For simplicity, suppose there were just 3 disks, and we’ll refer to the three needles as A, B, and C... We then move the top disk from C to A. Example (Ct’d) For simplicity, suppose there were just 3 disks, and we’ll refer to the three needles as A, B, and C... We then move the top disk from C to B. Example (Ct’d) For simplicity, suppose there were just 3 disks, and we’ll refer to the three needles as A, B, and C... We then move the top disk from A to B. Example (Ct’d) For simplicity, suppose there were just 3 disks, and we’ll refer to the three needles as A, B, and C... and we re done The problem gets more difficult as the number of disks increases...

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.