ࡱ> OQN#` #bjbj\.\. 7>>D>D----$-Dp76--------6666666$8h;\7%/--%/%/7--*7222%/--62%/62226-- @,}k-%/66@70p76j;1j;6j;68->4.,2`.$.---772 ---p7%/%/%/%/$d Recursion Recursive solutions Like top-down design, recursion breaks a problem down into several smaller problems The smaller problems are exactly the same type as the original problem Recursion and mirrors If you stand between two mirrors facing each other, how many images of yourself do you see? Are all the images exactly the same? Recursion is like these mirror images; each images is slightly smaller than the others A recursive solution solves a problem by solving smaller and smaller instances of the same problem Eventually, the new problem will be so small that its solution is known. This known solution helps solve each of the larger problems Form of recursive solutions 1. Every recursive call must make the problem smaller 2. Each smaller problem must be exactly the same as the original problem, only smaller 3. The problem must become small enough that you know the solution - this is called the base case 4. This strategy is called divide and conquer Questions to ask about recursive solutions Can you define the problem in terms of a smaller problem of the same type? Does each recursive call diminish the size of the problem? Do you know the instance of the problem to be the base case? As the problem size diminishes, will it reach the base case? Finding the factorial of a number What is a factorial? Factorial(5) = 5*4*3*2*1 Factorial(0) =1 Factorial(n) = n*(n-1)*(n-2)**1 The factorial of a negative integer is undefined Note: a recursive solution of this problem is not at all efficient But it is a good first example We will write this first as a function, then convert the function to an algorithm for a computer Recursively defined functions To define any function recursively: 1. Specify the value of the function at 0 or 1 - this is the problem so small that you know the answer; I.e. the base case 2. Give a rule for finding its value as an integer from its values at smaller integers To define the factorial function recursively: 1. factorial(1) = 1; (base case) 2. factorial(n) = n * factorial(n-1) Converting the function to an algorithm 1. factorial(1) = 1; (base case) 2. factorial(n) = n * factorial(n-1) int factorial(int n) if (n = 1) return 1; else return n*factorial(n-1); Searching There are basically two ways of searching: Start at the beginning, and look at every item until you find what you want This is called a sequential search Put the items in some sort of order, then search Look at the middle item, If the item is before, search the first half Else if after, search the second half Example: finding a word in a dictionary A pseudocode solution to the dictionary problem search(dictionary, aWord); if (dictionary is only one page, scan for aWord) else { Open dictionary near the middle decide which half contains aWord if (aWord is in first half) search(first_half, aWord) else search(second_half, aWord) Binary search: A recursive algorithm Binary search pseudocode if (array is of size 1) (item = value) or (not in array) else find the midpoint of the array find which half contains the item if (item is in first half) search(first_half, value) else search(second_half, value) Details to be considered in implementation How do you determine which half of the array contains the value? Find the value at the midpoint, then see if item is < or > the value at the midpoint Test to see if array[midpoint] is the value before recursive calls If youve found it, dont make the recursive calls How do you pass half an array in each recursive call? Pass the index values for first and last along with the array name Write the header for the method binary Search More details What should the base case be? When the array size is 1 (first > last); but is this the only base case? What if you find the value early? How do you indicate the result? What if the value is not found in the array? Look at Java code for binary search private static int binSearch(Object[ ] items, Comparable target, int first, int last) { int middle = (first + last) / 2; if (first > last) return -1; else { int result = target.compareTo(items[middle]); if (result == 0) return middle; else if (result < 0) return binSearch(items, target, first, middle - 1); else return binSearch(items, target, middle + 1, last); } } Quiz Write a recursive method to find a number raised to a power I.e. an = ? Base case: a0 = 1 Rule: an = a * a(n-1) Written in function notation: f(0) = 1; f(n) = a * f(n-1) Convert the function to an algorithm f(0) = 1; f(n) = a * f(n-1) int power(int a, int n) if n = 1 return a; else return a*power(a, n-1); Euclid's algorithm (finding the greatest common devisor) How would you find the gcd of 42 and 245? Euclid was a Greek who discovered a long time ago that If a and b are positive integers with a>b such that b is not a divisor of a, then gcd(a,b) = gcd(b, a mod b) Find the gcd of 378 and 4851 using this method. How could you write this as a function? As a method? Writing it as a recursive method Writing this as a recursive function Base case: gcd(a, b) = b if a mod b = 0 Rule gcd(a,b) = gcd(b, a mod b) Algorithm: public static int gcd(int a, int b) { if (a % b = = 0) { return b; } else { return gcd(b, a % b); } } Other recursive definitions Suppose a function f is defined recursively by: f(0) = 3 f(n) = 2*f(n-1) +3 What is f(5)? F(5) = 2*f(4) +3 F(4) = 2*f(3) + 3 F(3) = 2*f(2) +3 F(2) = 2*f(1) + 3 F(1) = 2*f(0) + 3 Recursion and iteration Recursion is an alternative to iteration Often they are more elegant and simpler than iterative solutions But not all recursive solutions are better than iterative solutions Some are so inefficient that it may take years on the fastest computers to solve. The overhead of recursion All method calls, recursive or not, have overhead Every method call produces an activation record The entire environment is pushed onto the system stack Recursive methods magnify this overhead since one method call can generate a large number of calls How many method calls result from fact(n)? From rabbit(n) Often, the clarity and elegance of recursive methods more than compensate for the additional overhead. Activation records or How the computer handles recursion A recursive call to a method is just like any other call to a method The system must keep tract of where to return when the method completes execution It needs to keep tract of the local environment for each method call. This includes: The return address The values of the arguments Any local variables The value to be returned It keeps this information on the runtime stack Looking at the runtime stack Assume we are running the method pow for this call: pow(2, 4) What will the runtime stack look like? int pow(int a, int n) if n = 1 return a; else return a*pow(a, n-1);   2 B ^ o  2 pqr4>ּǰ֟y"h6h65CJOJ\^JaJ&h6h65CJOJQJ\^JaJ h6h6CJOJQJ^JaJh6h6CJ\aJh65CJ\aJ h6h6h6CJaJh6h65CJ\aJh6h6CJaJ h6h6CJOJQJ^JaJ/ r, Q V < D  & Fgd6 & Fgd6gd6 & Fgd6gd6$a$gd6#  2 K [ } qr>9_gd6 & Fgd6 & Fgd6gd6gd6 & Fgd6UxqwHNv|89!pp^p^p"h6h65CJOJ\^JaJ"h6h65CJOJ\^JaJh6h65CJ\aJh6h65CJ\aJ&h6h65CJOJQJ\^JaJ&h6h65CJOJQJ\^JaJ+h6h65B*CJOJ\^JaJph"h6h65CJOJ\^JaJh6h6CJaJ h6h6$ UxAq & Fgd6 & Fgd6 & Fgd6 & Fgd6 & Fgd6 & Fgd6 & Fgd6gd6gd6gd689|!Cc>i & F gd6 & Fgd6 & Fgd6gd6 & Fgd6 & Fgd6gd6gd6 & Fgd6 %KhijĹ~hVhVh~D"h6h65CJOJ\^JaJ#h6h65B*CJ\aJph+h6h65B*CJOJ\^JaJph h6h6h65CJ\aJh6h6CJH*aJh6h65CJH*\aJh6h65CJ\aJh6h6CJaJ&h6h65CJOJQJ\^JaJ/h6h65B*CJOJQJ\^JaJphh6h6B*CJaJphiP%CijHr & Fgd6 & F gd6gd6gd6 & Fgd6gd6gd6L+6'5Kbxgd6 & Fgd6 & F gd6gd6 & Fgd6gd6 & Fgd6+6'x!y!z!!!""#########о鯣ޛޛ޾ރ޾оо h6h6CJOJQJ^JaJ h6h6h6CJaJh6B*CJaJphh6h6B*CJaJph"h6h65CJOJ\^JaJh6h65CJ\aJh6h6CJaJ+h6h65B*CJOJ\^JaJph")m = t !y!z!!!J"""""",#-#J# & Fgd6gd6 & Fgd6gd6gd6 & Fgd6J#######gd6gd6 & Fgd6 & F gd650P:p6/ =!"#$% @@@ NormalCJ_HaJmH sH tH T`T 6 Heading 17$8$@&H$5CJ(OJQJ\^JaJ(R`R 6 Heading 27$8$@&H$^`CJ aJ R`R 6 Heading 3I7$8$@&H$^I`CJaJJ`J 6 Heading 4L7$8$@&H$^`LDA@D Default Paragraph FontRi@R  Table Normal4 l4a (k(No List> r,Q V<D2K[}qr>9_ U x   A q  8 9|!Cc>iP%CijHrL+6'5Kbx)m =tyzJ,-J00 0  000 0 0 0 0 0 000 0 0  0 ( 0 : 000 0  0 0 000 0( 0( 0( 0( 0 0( 0 000 0m0m0m0m 0m0m0m000 0 0 0 000 0( 08 0  0( 0q 8 0 8 0! ( 0"q 0 0#  0$  0%  000 0 0(  000 0* ( 0+  0, ( 0-  0. ( 0/  00 0 0 01( 028 03( 04 05 06 07000000000 080 09 0: 0;(000 0<` 0=`0`0`0`00 0> 0?( 0@h0 0A 0B00 0Cx0x0x 0Dx 0 00 0F 0G 0H 0I 0J 0K 0L 0M 000 0O 0P 0Q 0R00 0S 0T 0U 0V 0W 000 0 0 0( 0( 0( 0( 0 000 0 0 0000 r,Q V<D2K[}r>9_ U x   A q  8 9|!Cc>iP%CjHrL+6'5Kbx)m =tzJ,-J00 0  0 0 0 0 0 0 0 00 0 0  0 ( 0 : 0 0 0  0 0 00 0( 0( 0( 0( 0 0( 0 00 0m0m0m0m 0m0m0m00 0 0 0 0 0 0( 08 0  0( 0q 8 0 8 0! ( 0"q 0 0#  0$  0% @ 0&  @0 0'  0(  0) 0 0* ( 0+  0, ( 0-  0. ( 0/  00 0 0 01( 028 03( 04 05 06 07000000000 080 09 0: 0;*00 0<` 0=`0`0`0`0 0> 0?( 0@g0 0A 0B00 0Cw0w0w 0Dw 0Ew0 0F 0G 0H 0I 0J 0K 0L 0M 0N0 0O 0P 0Q 0R00 0S 0T 0U 0V 0W 0X 0 0Yl 0Zl 0[l( 0\=( 0]=( 0^=( 0_= 0`l0l0 0a  0b  0c 0 0 0# iJ###k \( k Tk  + k + rrxx8*urn:schemas-microsoft-com:office:smarttagsCity9*urn:schemas-microsoft-com:office:smarttagsplace 4u 2<KU[e?Icmq x   FHquuKM!t6</1:<PRgi}33333333333333333333333333333333333333333333333333333[r ht+6-JP* d x h  1 lD D E pE E  F xF  @CJ OJQJ^Jo(" $ @CJOJQJ^Jo(" t  @CJOJQJ^Jo( 1 @CJOJQJ^Jo( 1 @CJOJQJ^Jo(" xD @CJOJQJo(" D @CJOJQJ^Jo(" $E h@CJOJQJ^Jo(" |E @CJOJQJ^Jo(" E @CJ OJQJ^Jo(" ,F @CJ$OJQJ^Jo(" F @CJOJQJ^Jo(" ` K-*SummaryInformation(>DocumentSummaryInformation8FCompObjq  FMicrosoft Office Word Document MSWordDocWord.Document.89q