INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS102, SECTIONS 52, 54 & 55  (001 Semester)

INTRODUCTION TO COMPUTING

LAB  #08 More on Methods with Parameters and Recursion

 

Instructor: Bashir M. Ghandi

 


Objectives:

To gain experience with:

 

1.  Objects as parameters

All the methods we saw in the last lab involved only primitive types as parameters.  However, objects can be passed as parameters to a method.  In fact, we have been passing object as parameters in our programs.  For example, each time the draw or fill method of the Graphics/Grapics2D class is called, a graphic shape object is passed as a parameter.

Rectangle square = new Rectangle(10,10,50,50);

g2.fill(square).

 

This means the fill method of the Graphics class must have been declared similar to:

public void fill (Rectangle rect)

 

However, there is one fundamental difference between passing an object as parameter and passing a primitive type as parameter.  Before we examine this difference, let us first understand what exactly happened when a primitive type variable is declared and when an object variable is created.

 

We recall that if a variable of primitive type is declared, memory is allocated for the variable depending on its type.

        E.g.  int age; à

if we now assign a value to the variable, the value is stored in the memory:

        E.g.   age=30; à

On the other hand, when an object variable is declared, the memory that is allocated is only enough to hold the address (some times called reference) of the object.  The memory for the actual object, which will contain its fields and method is not allocated until the object is created.

        E.g.         Rectangle square;  à 

Now, if an object is created using:  new Rectangle(10, 10, 50, 50);

Then memory is created for the object to hold all the fields and methods of the object.  The address of the first byte of that memory (say location 1000) is stored in the reference variable square.

It is important to note that the variable square is not the object.  It is only a reference (the address) of the object.

 

Now the difference between passing primitive types and objects as parameters is that primitive types are passed by value, while object are passed by reference.  Thus, in case of primitive types, the value of the actual parameter is copied to the formal parameter and any change to the formal parameter will not affect the actual parameter.

 

In case of objects however, it is the address of the actual object that is copied to the formal parameter.  Now since the called method has access to the address of the actual objects, it can use that to access and modify the state (fields) of the actual object if it so wish.

 

Example 1:  The following program passes two integer values to a method swap so that the two values are interchanged.  At first glance it appeared as if it will work, but actually it doesn’t since the changes in the method do not affect the actual parameters.

import java.io.*;

import TextIO;

 

class SwapPrimitives {

   static TextIO inputStream = new TextIO(System.in);

 

   static void swap(int first, int second) {

      int temp;

     

      temp=first;

      first=second;

      second=temp;

   }

 

   public static void main (String[] args) throws IOException {

     int num1, num2;

    

      System.out.print("Enter two integer numbers:");

      num1 = inputStream.readInt();

      num2 = inputStream.readInt();

     

      System.out.println("\nValues before swapping are: "+num1+" and "+num2);

      swap(num1, num2);

      System.out.println("Values before swapping are: "+num1+" and "+num2);

   }

}

 

To solve this problem, we can create objects containing the integer numbers and pass them to the swap method instead.  Before we do this, we briefly introduce how to create classes that can be use to create objects.

 

2.  Brief introduction to object classes

The classes we have written so far are all static classes.  That is, they contain only static methods, thus, they cannot be used to create objects.  While we cannot completely avoid the use of static classes, their use is in fact bad as far as object-oriented approach to problem solving is concerned.  This approach, is primarily about working with objects, thus, we should as much as possible try to create classes that can be used to create objects rather than static classes.  We shall learn more about this in Lab # 11, for now let us introduce the things we need to know to create these types of classes.

 

Variables and Methods should be non-static:

When creating object classes, we must declare the variables and methods that we wish to belong to objects as non-static.  That is, they should not have the word static in their definition.  Such variables and methods are usually called instant variables and instant methods, as they only exist when an object of the class is created.

 

Constructors:

When an object is created, the instant variables of the object are automatically initialized to some default values (e.g. 0 for numeric variables).  If we want to initialize these variables with different values, then we have to declare what is called a constructor.  Constructors are similar to methods except for the following:

·         They do not have any return type (not even void)

·         Thy must have the same name as the class

There can be any number of constructors for a class provided each has a different signature (different formal parameters).

 

Example 2: The following example solves the swapping problem by first defining a class containing an integer variable and passing objects of this class to the swap method.

 

import TextIO;

 

class MyInteger {

      int n;

     

      public MyInteger(int number) {

            n=number;

      }

}

 

public class SwapObjects {

      static TextIO inputStream = new TextIO(System.in);

 

      static void swap(MyInteger first, MyInteger second) {

            int temp;

           

            temp=first.n;

            first.n=second.n;

            second.n=temp;

      }

 

      public static void main (String[] args) throws IOException {

            int num1, num2;

    

            System.out.print("Enter two integer numbers:");

            num1 = inputStream.readInt();

            num2 = inputStream.readInt();

            MyInteger intObject1 = new MyInteger(num1);

            MyInteger intObject2 = new MyInteger(num2);

           

            System.out.println("\nValues Before swapping are: "+num1+" and "+num2);

            swap(intObject1, intObject2);

            System.out.println("Values After swapping are: "+intObject1.n+" and

                                                             "+intObject2.n);

      }

}

 

3.  Introduction to Recursion:

So far, we have seen that the execution of an application begin with the main method, which may call other methods, which may call other methods, etc.

Now Java also allows a method to call itself.  This is called recursion and such methods are called recursive methods.

Recursion is essentially another way of performing iteration and it is a very powerful tool for simplifying algorithms and coding of methods that involve repetitions.

 

A well-defined recursive method has:

·         a base case.

·         a recursive step, which must always get “closer” to the base case from one invocation to another.

 

Each call to a recursive method sets up a new execution environment, with new parameters and local variables.

When the method completes, control returns to the method that invoked it (which may be an earlier invocation of itself).

 

Example 3:  The following is a recursive method that computes the factorial of an integer n. Notice that the method looks very similar to the mathematical definition.  This elegance is one of the beauty of recursion.

.import java.io.IOException;

import TextIO;

 

class Factorial {

      static TextIO inputStream = new TextIO(System.in);

     

      public static int factorial(int n) {

            if (n == 0)

               return 1;

            else

               return n*factorial(n-1);

      }

 

      public static void main (String[] args) throws IOException {

            int n, answer;

           

            System.out.print("Enter an integer:");

            n = inputStream.readInt();

            answer = factorial(n);

            System.out.println("The factorial of "+ n + " is " + answer);

  }

}

Factorial: A Sample Trace

 

factorial (6) = (6*factorial(5))

     = (6*(5*factorial(4)))

    = (6*(5*(4*factorial(3))))

    = (6*(5*(4*(3*factorial(2)))))

    = (6*(5*(4*(3*(2*factorial(1))))))

    = (6*(5*(4*(3*(2*1)))))

    = (6*(5*(4*(3*2))))

    = (6*(5*(4*6)))

    = 6*(5*24))

    = (6*120)

    = 720

 

Example 4:  The following is a recursive method that computes the nth fibonacci number which is defined as follows:

 

1  for n=0

 

 

fibonacci(n) = 

1 for n=1

 

 

fibonacci(n-1)+fibonacci(n-2)  for n>1

 

 

import java.io.IOException;

import TextIO;

 

class Fibonacci {

      static TextIO inputStream = new TextIO(System.in);

 

      static int fibonacci (int num) {

            if (num == 0 || num == 1)

                  return 1;

            else

                  return (fibonacci(num-1) + fibonacci(num-2));

      }

 

      public static void main (String[] args) throws IOException {

            int n, answer;

            System.out.print("Enter an integer:");

            n = inputStream.readInt();

            answer = fibonacci(n);

            System.out.println("The "+n+ "th Fibonacci number is: "+ answer);

      }

}

 

The next example requires the knowledge of some methods of the standard class String.  We shall study String in detail in the next lab, but for now, here are some of its basic methods.

length()

returns the number of characters in the string

charAt(n)

returns the character at position n assuming the first character is at position 0.

substring(n)

returns a string starting from position n to the end of the string (again counting is assumed to begin from 0)

substring(n1,n2)

returns a tring starting from n1 to n2-1.

equals(stringvar)

returns true if this string is eqaul to the string in stringvar. (Note:All objects are compared using this method)

 

Example 3:  The following example is a recursive method that checks whether a character is contained in a string

.import java.io.IOException;

import java.io.*;

import TextIO;

 

class Member {

      static TextIO stdin = new TextIO(System.in);

 

      static boolean isMember(char ch, String str) {

            if (str.length()==0)

                  return false;

            else if (ch == str.charAt(0))

                  return true;

            else

                  return isMember(ch, str.substring(1));

      }

 

      public static void main (String[] args) throws IOException {

            char ch;

            String str;

    

            System.out.print("Enter your string (one word!): ");

            str = stdin.readString();

            System.out.print("Now enter the character you wish to search for: ");

            ch = stdin.readChar();

           

            if (isMember(ch, str))

                  System.out.println(ch +" Is a member of "+str);

            else

                  System.out.println(ch +" Is NOT a member of "+str);

      }

}

 

3.  Assignments

1.       Write a recursive method sum(int n) that receives a parameter n as a parameter and returns the sum of the following series:

                                        1 + 2 + 3 + 4 + . . .+ n

       Write a main method that reads an integer from the user and calls your method to compute the sum and print the result.

2.        Write a recursive method power(double x, int n) that returns xn (Note: do mot use Math.pow method.  Write a main method that reads input from the user and calls your method to get the power and prints the result.

3.    The greatest common divisor (gcd) of a number can be defined recursively as follows:

 

m  if m<=n and m divides n

gcd(n, m) = 

gcd(m, n)   if m>n

gcd(m, n%m) if n>m and m does not divides n

 

 

Write a recursive method gcd(int n, int m) that returns the gcd of two numbers.  Write a main method that reads two integer numbers and calls your method to compute the gcd and print the result.

4.        A palindrome is a string that reads the same way both backwards and forwards. Example is madam. Write a boolean method isPalindrome(String s) that receives a string and returns true if the string is a palindrome and false otherwise.  Write a main method that reads a word from the user and prints a message stating whether or not the word is a palindrome.