Java code. Convert an iterative implementation to recursive implementation using

Question

Java code. Convert an iterative implementation to recursive implementation using the code provided:

**/
   public Record findRecordBinary(String name)
   {

       int lowerIndex, midIndex, returnIndex, upperIndex;
       Record returnValue = null;

       //added
       returnIndex = -1;

       lowerIndex = 0;
       upperIndex = this.recs.size()-1; //this. is available to everywhere and it was a method defined before.
       midIndex = (lowerIndex + upperIndex)/2;

       System.out.println(" start findRecordBinary("+name+")");

       while(lowerIndex <= upperIndex)
       {
           System.out.println("lowerIndex =("+lowerIndex+")="+ "upperIndex("+upperIndex+") ="+ " midIndex = ("+midIndex+")");
           String midName = this.recs.get(midIndex).getName();

           int midNameComp = midName.compareTo(name);

           if(0 > midNameComp)
           {
               System.out.println("midIndexName="+midName+""+" is less than "+name+" "+"so set lowerIndex to midIndex+1");
               lowerIndex = midIndex + 1;
           }

           else if(0 < midNameComp)
           {
               System.out.println("midIndexName="+midName+""+" is greater than "+name+" "+"so set upperIndex to midIndex-1");
               upperIndex = midIndex - 1;
           }
           else
           {
               System.out.println("midIndexName="+midName+""+" is equal to "+name+" "+"recordIndex found");
               returnIndex = midIndex;
               break;
           }
           midIndex = (lowerIndex + upperIndex)/2;
       }

       if( returnIndex >= 0)
       {
           returnValue = this.recs.get(returnIndex);

           System.out.println("found record " + returnValue);
       }else{ System.out.println(name + " not found");
       }

       return returnValue;
   }

Explanation / Answer

//This task can be done in two ways.
//1. creating recursive function in place of while loop
//       This doesn't affect the prototype of existing findRecordBinary
//2. Modifying the existing findRecordBinary as recursive function
//       Arguments of findRecordBinary() changes

// Both the solutions are available below

//1. Changing the iterative while loop as recursive function
public Record findRecordBinary(String name)
{
   int lowerIndex, returnIndex, upperIndex;
   Record returnValue = null;
   lowerIndex = 0;
   upperIndex = this.recs.size()-1; //this. is available to everywhere and it was a method defined before.
   System.out.println(" start findRecordBinary("+name+")");
  
   // recursive_Function calculates the midIndex
   // Pass lowerIndex and Upper Index to the recursive_Function
   // recursive_Function return the index of the record if found, else returns -1
   returnIndex = recursive_Function(name, lowerIndex, upperIndex);
  
   // The below code is not changed
   if( returnIndex >= 0)
   {
       returnValue = this.recs.get(returnIndex);
       System.out.println("found record " + returnValue);
   }
   else
   {
       System.out.println(name + " not found");
   }
   return returnValue;
}

int recursive_Function(String name, int lowerIndex, int upperIndex)
{
   int midIndex, returnIndex;
   returnIndex = -1;
   if(lowerIndex <= upperIndex)
   {
       midIndex = (lowerIndex + upperIndex)/2;
       System.out.println("lowerIndex =("+lowerIndex+")="+ "upperIndex("+upperIndex+") ="+ " midIndex = ("+midIndex+")");
       String midName = this.recs.get(midIndex).getName();
       int midNameComp = midName.compareTo(name);

       if(0 > midNameComp)
       {
           System.out.println("midIndexName="+midName+""+" is less than "+name+" "+"so call recursive_Function with midIndex+1 and upperIndex");
           // Call recursive_Function() with new lower and upper indices
           // and return the result to its caller
           return recursive_Function(name, midIndex+1, upperIndex);
       }
       else if(0 < midNameComp)
       {
           System.out.println("midIndexName="+midName+""+" is greater than "+name+" "+"so call recursive_Function with lowerIndex and midIndex-1");
           // Call recursive_Function() with new lower and upper indices
           // and return the result to its caller
           return recursive_Function(name, lowerIndex, midIndex-1);
       }
       else
       {
           System.out.println("midIndexName="+midName+""+" is equal to "+name+" "+"recordIndex found");
           returnIndex = midIndex;
       }
   }
   return returnIndex;
}

// 2. To convert findRecordBinary() as recursive function,
// lowerIndex and upperIndex should be passed as arguments
// The caller of findRecordBinary() calculates upperIndex using this.recs.size()-1
public Record findRecordBinary(String name, int lowerIndex, int upperIndex)
{
   int midIndex, returnIndex;
   Record returnValue = null;
   //added
   returnIndex = -1;
   System.out.println(" start findRecordBinary("+name+")");
   if(lowerIndex <= upperIndex)
   {
      
       midIndex = (lowerIndex + upperIndex)/2;
       System.out.println("lowerIndex =("+lowerIndex+")="+ "upperIndex("+upperIndex+") ="+ " midIndex = ("+midIndex+")");
       String midName = this.recs.get(midIndex).getName();
       int midNameComp = midName.compareTo(name);

       if(0 > midNameComp)
       {
           System.out.println("midIndexName="+midName+""+" is less than "+name+" "+"so call findRecordBinary with midIndex+1 and upperIndex");
           //call findRecordBinary with updated lower and upper indices
           // and return the result to its caller
           return findRecordBinary(name, midIndex+1, upperIndex);
       }
       else if(0 < midNameComp)
       {
           System.out.println("midIndexName="+midName+""+" is greater than "+name+" "+"so call findRecordBinary with lowerIndex and midIndex-1");
           //call findRecordBinary with updated lower and upper indices
           // and return the result to its caller
           return findRecordBinary(name, lowerIndex, midIndex-1);
       }
       else
       {
           System.out.println("midIndexName="+midName+""+" is equal to "+name+" "+"recordIndex found");
           returnIndex = midIndex;
       }
   }
   // The below code is not changed
   if( returnIndex >= 0)
   {
       returnValue = this.recs.get(returnIndex);
       System.out.println("found record " + returnValue);
   }
   else
   {
       System.out.println(name + " not found");
   }

   return returnValue;
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.