Report

Programming With Java ICS201 Chapter 11 Recursion University Of Ha’il 1 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 2 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 3 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 4 Programming With Java ICS201 Recursive Methods 0! n! 3! 2! 1! = = = = = 1 (By Definition!) n x (n – 1) ! If n > 3 x 2! 2 x 1! 1 x 0! 0! = 1 1! 2! 3! = = = 1 x 0! 2 x 1! 3 x 2! (Base Case!) = 1x1=1 = 2x1=2 = 3x2=6 0 Programming With Java ICS201 Recursive Methods • • recursive step: fact(n) = n * fact(n-1) base step: fact(0) = 1 fact(4) = 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 6 Programming With Java ICS201 Recursive Factorial Method 7 Programming With Java ICS201 Recursive Factorial Method public static int fact(int num) { if (num = = 0) return 1; else return num * fact(num – 1); } 8 Programming With Java ICS201 Fibonacci numbers n 0 1 2 3 4 5 6 7 8 9 10 11 Fib(n) 0 1 1 2 3 5 8 13 21 34 55 89 public int fib(int n) { if(n <= 1) { return n; } else { return fib(n - 1) + fib(n - 2); } } University Of Ha’il 9 Programming With Java ICS201 Convert from decimal to binary 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 10 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){ int i=10; dec2bin(i); } } University Of Ha’il Output: 1010 11 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 12 Programming With Java ICS201 Recursion or Iteration? Two ways to solve particular problem: Iteration Recursion Iterative control structures use looping to repeat a set of statements. Tradeoffs between two options: Sometimes recursive solution is easier. Recursive solution is often slower. 13 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 14