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


| Home | Hosting | Domains | Support |  Contacts |
|
Terms & Condition | Privacy Policy |


 

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

LasX.com | Garage Door Company | BidoBee.com | RushRash Inc