Google Answers Logo
View Question
 
Q: Java Programming with Recursion ( Answered,   0 Comments )
Question  
Subject: Java Programming with Recursion
Category: Computers > Programming
Asked by: math01-ga
List Price: $20.00
Posted: 15 Feb 2003 01:32 PST
Expires: 17 Mar 2003 01:32 PST
Question ID: 161650
Description
In this problem, write several recursive methods as a part of a class
called Recursion. Write appropriate code to test them as a part of the
"main" method. The methods as described below are not necessarily
related, but should be made part of the same class for convenience.

Write a method called NumberofDigits that returns the number of digits
in an integer.

Write a method called SumRange that takes two arguments n and m and
returns the sum of all integers from n to m, both inclusive.

Write a method called Palindrome that checks if a given string is a
palindrome. It should return a Boolean value. A string is a palindrome
if it reads the same forwards and backwards (e.g. "abba").

Write a method called Countdown that takes a number n as it argument
and prints out the numbers in a decreasing order (one per line)
starting with n all the way down to 0.

Write a procedure called Howmany that takes two arguments: an array
(of integers) and an element (integer) and returns the number of times
the elements occurs in the array.

Procedure
Write a class called "Recursion" with the five methods as describe
above.
Write a main method and write the necessary code to test the
correctness of each method.
Make sure that at least one of the recursive methods is
tail-recursive.
Answer  
Subject: Re: Java Programming with Recursion
Answered By: theta-ga on 16 Feb 2003 11:06 PST
 
Hi math01-ga,
    Welcome back! :-)
    As usual, I have provided the required Java code below. To compile
and run
this code, you will need the Java2 SDK. You can download the Java SDK
from :
        - Download : Java(TM) 2 SDK, Standard Edition, v 1_4_0_03 
          ( http://java.sun.com/j2se/1.4/download.html ) 
 
   A free Java IDE (if you need one) can be found at : 
        - The RealJ Java IDE 
          ( http://www.realj.com ) 
 
   The code provided below has been tested with RealJ and JDK 1.4.

+-----------------------------------------+

  Copy the given code into a file called 'Test.java'. The code
contains the following classes:
   + class Test
   |    |_____main(String args) :This method tests the recursion
methods.
   |
   + class Recursion
        |----NumberOfDigits(int)
        |----SumRange(int,int)
        |----Palindrome(String)
        |----Countdown(int)
        |----Howmany(int[],int)

+-----------------------------------------+

The recursion methods are pretty simple and pretty much self
explanatory. If you have problem following the flow of the program,
just ask me for a clarification and I will help you out.
As for the requirement of atleast one tail recursive function, the
function Countdown() meets your needs. For a definition of the term
"tail recursion", check out:
      - NIST: tail recursion
        ( http://www.nist.gov/dads/HTML/tailrecursn.html )

So, without further delay, here is the code:

+-----------------------------------------+

import java.io.*;


// Test Class: Contains the main method which tests
//             the methods of the Recursion class.
public class Test
{
  public static void main(String args[]) throws IOException
  {
    // Setup out keyboard reader
    BufferedReader buf =  
            new BufferedReader(new InputStreamReader(System.in));

    // Create Recursion class object
    Recursion R = new Recursion();
	 
    int choice = 1;
	 
    while( choice!=0 )
    {
       do
	{
	  System.out.print( "\n\n\tRecursion Test Menu"
	     + "\n 1. Test Function NumberOfDigits()"
	     + "\n 2. Test Function SumRange()"
	     + "\n 3. Test Function Palindrome()"
	     + "\n 4. Test Function Countdown()"	        	        
	     + "\n 5. Test Function Howmany()"	        
	     + "\n 0. Exit"
	     + "\n\nEnter Your Choice(0-5): ");
	     
	  choice = Integer.parseInt( buf.readLine() );
	}while( choice<0 || choice>5 );
	    
	switch(choice)
	{
	 case 1:	 
           System.out.println(" Testing Function NumberOfDigits() :");
           System.out.print(" Enter a number: ");
           int num = Integer.parseInt( buf.readLine() );
           System.out.println(" The number " + num + " has "
                         + R.NumberOfDigits(num) + " digits.");
           break;
          
        case 2:
          System.out.println(" Testing Function SumRange() :");
	  System.out.print(" Enter a number n: ");
      	  int n = Integer.parseInt( buf.readLine() );
	  System.out.print(" Enter a number m: ");
	  int m = Integer.parseInt( buf.readLine() );
	  System.out.println(" The sum of numbers from "+n
	                    +" to "+m+" is "+R.SumRange(n,m));
	  break;
	     
	case 3:
     	  System.out.println(" Testing Function Palindrome() :");
	  System.out.print(" Enter a string : ");
	  String str = buf.readLine();
	  System.out.println(" The function returned " 
	                     + R.Palindrome(str) + ".");
	  break;
		     
	case 4:              
          System.out.println(" Testing Function Countdown() :");
          System.out.print(" Enter a number: ");
          int count = Integer.parseInt( buf.readLine() );
          System.out.println(" The output of this function is: ");
          R.Countdown(count);
          break;

        case 5:
          System.out.println(" Testing Function Howmany() :");
          System.out.print(" Enter the number of array elements: ");
          int arrLen = Integer.parseInt( buf.readLine() );
          if( arrLen==0)
             break;
          // Create array and populate it
          int[] array = new int[arrLen];
          for(int i=0; i<arrLen; i++)
          {
            System.out.print(" Enter array element "+i);
            array[i] = Integer.parseInt( buf.readLine() );
          }
          System.out.print(" Enter the number to search for: ");
          int search = Integer.parseInt( buf.readLine() );
          System.out.println(" The number " +search
                           + " appears in the array "
                           + R.Howmany(array,search)+ " times.");
          break;
       } // end Switch Case
       
       // Pause after showing function output
       if( choice!=0 )
       {
         System.out.print("\nPress ENTER to continue....");
         buf.readLine();
       }
          
     }// End While
  } 
  
}


// Recursion Class: Contains the 5 recursive methods
class Recursion
{  
  // NumberofDigits: returns the number of digits in an integer.
  // Divides a number by 10 in a recursive loop,
  // adding 1 everytime until the number becomes 0.
  public int NumberOfDigits(int num)
  {
    num = num/10;
    if( num == 0)
       return 1;
    return ( 1+NumberOfDigits(num) );
  }
  
  
  //SumRange: takes two arguments n and m and returns the sum
  //          of all integers from n to m, both inclusive
  public int SumRange( int n, int m )
  {
    // Make sure that n <= m
    if( m<n)
    {
      // Swap values
      int temp = m;
      m=n;
      n=temp;
    }
    
    if( n == m)
       return n;
       
    return (n + SumRange( n+1,m ));
  }
  
  
  // Palindrome: checks if a given string is a palindrome. 
  //  Compares the first & last characters in a string
  //  If they are the same, it removes them and calls itself again.
  public boolean Palindrome( String str )
  {
    int strlen = str.length();  // length of the input string
    
    // A string of length 0 or 1 is always a palindrome
    if( strlen==0 || strlen == 1 )
       return true;
    
    if( str.charAt(0) == str.charAt(strlen-1) )
       return ( Palindrome(str.substring(1, strlen-1)) );
    
    return false;
  }
      

  // Countdown: takes a number n  and prints out the numbers
  //            in a decreasing order(till 0)
  public void Countdown ( int n )
   {
     System.out.println( n );

     if(n==0)
        return;

     Countdown(n-1);
   }
   
   
  //Howmany: takes two arguments, an array (of integers) & an integer
&
  //         returns the no. of times the integer occurs in the array.
  public int Howmany ( int[] array, int n )
  {
    if( array.length == 1 )
      if( array[0] == n )
         return 1;
      else
         return 0;
    
    // Create new array
    int[] newArray = new int[array.length-1];
    // Copy Array
    for(int i=0; i<newArray.length; i++)
        newArray[i] = array[i+1];
    
    // Check if n is in the current element
  	 if( array[0] == n )
	    return 1+Howmany(newArray,n);
	 else
	    return Howmany(newArray,n);
  }
  
}

+-----------------------------------------+

Hope this helps.
If you need any clarifications, just ask!

Regards,
Theta-ga

==========================================
Google Search Terms Used:
      "tail recursion"
Comments  
There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy