#### Transcript chapter 3

Programming With Java ICS201 Chapter 11 Recursion University Of Ha’il 1 Programming With Java ICS201 Definition Recursion is a powerful concept that helps to simplify the solution of complex problems. Recursion means defining something in terms of itself. This means that the solution of a problem is expressed in terms of a similar problem but simpler. That is, solving the simpler problem leads to the solution of the original one. Recursive solutions are shorter, easier to understand and implement. University Of Ha’il 2 Programming With Java ICS201 Recursive Methods o A recursive method is a method that calls itself directly or indirectly. o A recursive method has two major steps: 1.recursive step in which the method calls itself 2.base step which specifies a case with a known solution o The method should select one of two steps based on a criteria: Example: recursive step: fact(n) = n * fact(n-1) base step: fact(0) = 1 University Of Ha’il 3 Programming With Java ICS201 Recursive Methods o The recursive step provides the repetition needed for the solution and the base step provides the termination. o Executing recursive algorithms goes through two phases: 1. Expansion in which the recursive step is applied until hitting the base step 2. “Substitution” in which the solution is constructed backwards starting with the base step University Of Ha’il 4 Programming With Java ICS201 Recursive Methods • • • fact(4) recursive step: fact(n) = n * fact(n-1) base step: fact(0) = 1 = 4 * fact(3) = 4 * (3 * fact(2)) = 4 * (3 * (2 * fact(1))) = 4 * (3 * (2 * (1 * fact(0)))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) =4*6 = 24 University Of Ha’il 5 Programming With Java ICS201 Constructing Recursion o To construct a recursive algorithm you have to find out: 1.Recursive step 2.Base step o A selection structure is then used to determine which step to take. University Of Ha’il 6 Programming With Java ICS201 General Algorithm if (stopping condition) then solve simple problem (base) else use recursion to solve smaller problem combine solutions from smaller problem University Of Ha’il 7 Programming With Java ICS201 Benefits of Recursion o Recursive methods are clearer, simpler, shorter, and easier to understand. o Recursive programs directly reflect the abstract solution strategy (algorithm). University Of Ha’il 8 Programming With Java ICS201 When To Use Recursion o The problem definition is recursive. o The problem is simpler to solve recursively. o When the produced results are used in the reverse order of their creation. University Of Ha’il 9 Programming With Java ICS201 When Not To Use Recursion o The recursion can be replaced with only a loop. o Run -Time or space limitation. University Of Ha’il 10 Programming With Java ICS201 Infinite Recursion o Recursion resembles loops in that it terminates based on the condition. o Missing the condition leads to infinite recursion. o The recursive step must introduce a simpler version of the problem leading to the base. o Infinite recursion occurs as a result of not introducing simpler problem. University Of Ha’il 11 Programming With Java ICS201 Recursion Removal o Recursion can be removed by replacing the selection structure with a loop o If some data need to be stored for processing after the end of the recursive step, a data structure is needed in addition to the loop. o The data structure vary from a simple string or an array to a stack. University Of Ha’il 12 Programming With Java ICS201 Example (Recursion) This method converts an integer number to its binary equivalent. Base step: dec2bin(n) = n if n is 0 or 1 Recursive step: dec2bin(n) = dec2bin (n/2) , (n mod 2) Algorithm dec2bin(n): If n < 2 else Print n dec2bin(n / 2) Print n mod 2 University Of Ha’il 13 Programming With Java ICS201 Example (Recursion) class Method { public static void dec2bin( int n){ if ( n < 2 ) System.out.print( n ); else { dec2bin( n / 2 ); System.out.print( n % 2 ); } } } class Dec2Bin{ public static void main(String [] arg){ } dec2bin(i); } Output: 1010 int i=10; University Of Ha’il 14 Programming With Java ICS201 Example (iterative) public static void dec2bin(int n){ String binary =""; while ( n >= 1 ){ binary = n%2 + binary; n /= 2; } System.out.print(binary); } University Of Ha’il 15 Programming With Java ICS201 Example : Vertical Numbers Output: 3 1 2 1 2 3 University Of Ha’il 16 Programming With Java ICS201 The Recursive Method power University Of Ha’il 17 Programming With Java ICS201 Exercise 1. Write a recursive method to find the greatest common divisor (GCD) of two integer n and m. 2. Write a recursive method to find Xn given the double X and the integer n. 3. Consider a Boolean array b filled with Boolean values. Write a recursive method boolean allTrue() that returns true if all values are true and returns false otherwise. University Of Ha’il 18