   Home Hosting Domains Support Contacts    Java Tutorial Home 2 3 4 5 6 7 8 9

# Java Recursion

 Topics -  Simple recursion -  Recursion with a return value. -  Binary search revisited. -  Recursion versus Iteration. -  Big problem reduce to a simple case or base case.   Factorial example 5! = 5 * 4 * 3 * 2 * 1 4! = 4 * 3 * 2 * 1 3! = 3 * 2 * 1 2! = 2 * 1 1! = 1 this is base case   5!                120 5! = 5 * 4!       24 5! = 5 * 4 * 3!         6 5! = 5 * 4 * 3 * 2!     2 5! = 5 * 4 * 3 * 2 *1! 1     A for loop will solve this problem. We can also solve this recursively.  You reduce the size of the problem each time you solve for a factorial.  The reduction is the general case?  The reduced is the base case.  .   Java Text Books Recursive methods -  Method that invokes itself. -  The arguments passed to the recursion take us closer to the solution with each call.   Coding the recursive Method. -  Factorial   n! = n * (n-1)!        * (n-1) * (n-2)!              *   public class RecursiveFactorial {   public static void main( String [] args )   {     // compute factorial of 7 and output it     System.out.println( "Factorial ( 7 ) is "                       + factorial( 7 ) );   }     public static int factorial( int n )   {     if ( n <= 0 )  // base case      return 1;     else    // general case      return ( n * factorial ( n - 1 ) );   } }   -  Start handling the base case first, example uses 0 not 1 which is more  mathematically correct.  Compiler hangs on to the value of the method but because it can't solve it, it starts building a stack and tries to solve it by continuing to call itself and keeps a record in memory called an activation record   1*fact(0) this returns 1 as above and now stack executes the returns 2*fact(1) this returns 2 3*fact(2) this returns 6 4*fact(3) this returns 24 5*fact(4) this returns 120   This generates a lot of memory, more than the for loop.  Some argues that recursion is more readable.     Recursive binary search code -  Take four parameters, array reference, key, beginning and end.   Recursion versus iteration -  Efficiency is slower. -  Readability and maintenance is supposed to be better.

Java Tutorial Home 2 3 4 5 6 7 8 9

Java Tutorial

Copyright © 2005 by HostItWise.com Read our Copyright. All rights reserved.