Chapter 7

 

1. Recursion

What is Recursion?

Why Recursion?

How?

A General Recursive Situation    

What is a base case?

2. Recursion in Java

A Simple Example

More Examples    

       Example1: Factorial   

       Example2: Sum

       Example3: Power

       Example4: Prime

       Example5: Palindrome       

3. Common Recursion Errors      


Recursion


What is Recursion ?

 

Recursion is another control mechanism. It consists of a method calling itself repeatedly until a terminating condition becomes true.

 

Why Recursion?

 

A program that solves a certain problem can be written easily using recursion.
 

How?

 

Let's say we have a problem that we would like to solve recursively. This is done by dividing the problem into smaller parts (sub-problems), then dividing these smaller parts into even smaller parts... and so on. Finally, the problem will be solved.

 

A General Recursive Situation

 

The problem: We would like to divide a line into 16 equal segments.

 

What would we do ? First ,we divide the line in half.

 

Simplifying the problem:

The problem can be now simplified into 2 smaller sub-problems:

1- divide the first segment into 8 equal pieces

2- divide the second segment into 8 equal pieces

 

 

How can we solve these 2 sub-problems?

By applying the same process (divide each of these segments in half).     

 

 

So now we have 4 equal segments. Now what?

 

Simplify even more :

Apply the same process again (divide each of the 4 segments in half)

 

Are we Done?

No, we only have 8 equal segments.

 

So, what do we do Now?

Repeat the same process again (divide each of these 8 segments in half)

 

 

So basically, this is what we have done:

Our process is dividing the line in half, we kept performing this process repeatedly until we finally solved our problem.

 

This can be expressed, recursively in a mathematical  format:

 

Divide(1) = 1*2=2

Divide(2) = 2*2=4

Divide(3) = 4*2=8

Divide(4) = 8*2=16

 

A more general formula can be :

 

                                   Divide(N) = Divide(N-1)*2

 

What is a base case ?

 

Any recursive method must have a base case. The base case is simply the terminating condition upon which we will stop calling the method.

In this example, the base case would be reaching 16 equal segments.

 

Recursion in Java

A recursive method, simply put, is a method that calls itself from inside its own body.

 

A Simple Example:

 

Lets say we want to count the number of pins in a pyramid of bowling pins, knowing that:

      The first row has one pin

      The second row has 2 pins

      The third row has 3 pins

      ... and so on.

We want to calculate the total number of pins in the triangle at any time.

The arrangement of the triangle has the following structure:

 

  * * * * *

   * * * *

     * * *

      * *

        *

 

Thinking Recursively:

When writing any recursive method, we must determine 2 things:

 

1- The base case >>> when we reach this case, we are done

2- The Formula >>> we use this to calculate all other cases (other than the base case)

 

Now lets try putting these 2 things in mind and re-thinking about the problem. Our aim is to find the total number of pins in the triangle at any given time. Therefore, we can fill out the following table:

 

Number of rows

Total # of Pins in Triangle

Formula

1

1

Base case

2

3

CountPins(2)  =  2 + CountPins(1)

3

6

CountPins(3)   = 3 + CountPins(2)

4

10

CountPins(4)   = 4 + CountPins(3)

5

15

CountPins(5)   = 5 + CountPins(4)

6

21

CountPins(6)   = 6 + CountPins(5)

CountPins(N)   = N + CountPins(N-1)

 

From the above table, we can conclude  that, to calculate the total number of pins in the triangle, we simply add the row number to the already existing pins. This is how we figured out the general formula. Now let us look at the simplification of one of the cases: 4 rows. 

 

                                CountPins(4) = 4 + CountPins(3)

                                                  = 4 + ( 3 +CountPins(2) )

                                                  = 4 + ( 3+ (2 +CountPins(1) ) )     [We reached the base case]

                                                  = 4 + ( 3+ (2 + 1) ) )

                                                  = 10

                                                  

The following is the method CountPins that implements this recursive function. The method takes in the number of current rows in the triangle and returns their total number.

 

      public class Triangle
      {
        static int CountPins(int row)
          {

            if (row == 1)

              return 1;
            else
              return (CountPins(row-1)+row);
           }
        public static void main(String[] args)
        {
                   

           int currentRows;
           String inData;
           
           InputStreamReader inStream = new InputStreamReader( System.in );
           BufferedReader stdin = new BufferedReader( inStream );
           System.out.print("How many rows does the triangle currently have? ");
           inData = stdin.readLine();
           currentRows = Integer.parseInt( inData );
          
           System.out.println
("The total number of pins in "+currentRows+" row(s) is "+CountPins(currentRows));
 

         }
        }
 

Sample Runs:

Run#1:

How many rows does the triangle currently have? 1
The total number of pins in 1 row(s) is 1

Run#2:

How many rows does the triangle currently have? 2
The total number of pins in 2 row(s) is 3

Run#3:

How many rows does the triangle currently have? 3
The total number of pins in 3 row(s) is 6

Run#4:

How many rows does the triangle currently have? 4
The total number of pins in 4 row(s) is 10

Run#5:

How many rows does the triangle currently have? 5
The total number of pins in 5 row(s) is 15

Run#6:

How many rows does the triangle currently have? 10
The total number of pins in 10 row(s) is 55

Run#7:

How many rows does the triangle currently have? 500
The total number of pins in 500 row(s) is 125250
 

Now that we know the general idea, let's take a look at some examples:

Examples

 

Example1
In this example, we want to write a method that calculates the factorial function recursively.

 

Thinking Recursively:

1- The base case

    We know that the factorial of 0 is 1

    Therefore, this is the base case.

2- The Formula

    The factorial of any number n can be written as

                                 

Fact(n) = n*(n-1)*(n-2) *..... *1

 

Number

Fact(n)

Formula

0

1

                             Base Case

1

1

Fact(1) = 1 * Fact(0)

2

6

Fact(2) = 2 * Fact(1)

3

24

Fact(3) = 3 * Fact(1) * Fact(0)

4

120

Fact(4) = 4 * Fact(3) * Fact(2) * Fact(1)

5

720

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

Fact(n) = n * Fact (n-1)

 

               The following is the recursive method Fact:     

import java.io.*;
public class RecursiveFactorial
{
    static int Fact(int n)
    {
         if (n==0)
              return 1;
         else
              return (n*Fact(n-1));

     }
public static void main(String[] args) throws IOException
{
    int num;
    String inData;
 

    InputStreamReader inStream = new InputStreamReader(System.in);
    BufferedReader stdin = new BufferedReader( inStream );

    System.out.print("Pleae enter n: ");
    inData = stdin.readLine();
    num = Integer.parseInt( inData );
 

    System.out.println("The factorial of "+num+" is "+Fact(num));

 }
}

Sample Runs:

Run#1:

Please enter n: 3
The Factorial of 3 is 6

Run#2:

Please enter n: 4
The Factorial of 4 is 24

Run#3:

Please enter n: 0
The Factorial of 0 is 1

 

 

 

Example 2

 

In this example, we want to write a method that, given 2 numbers, will find the sum of all the integers between them.                     

In other words: Given 1 & 4, the method should add 1+2+3+4 = 10

 

Thinking Recursively

1- The base case

We know that if the first and last number are equal, then their sum is simply one of them.

For example, if I say that I want to sum the numbers between 4 and 4, the sum will simply be 4.

Therefore, our base case occurs when the first number equals to the last number.

2- The Formula

If we want to sum the numbers from 3 to 6, then we would add 3+4+5+6 = 18

A more general formula can be written as :

 

                    first+(first+1)+(first+2)+...+(last-2)+(last-1)+last

Recursively

                   Sum(first,last) = Sum(first,last-1) + last

 

Now, lets take a look at the code of the function Sum which implements this formula.

 

 

           import java.io.*;
           class RecursiveAddition
           {
             public static int Sum(int a, int b)
             {
                 if (a==b)

                     return a;
                 else
                     return Sum(a,b-1)+b;

                        

             }

   

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

           {
                String inData;
                int first,last;

                InputStreamReader inStream = new InputStreamReader( System.in );
                BufferedReader stdin = new BufferedReader( inStream);
               
                System.out.print("Enter first number: ");
                inData = stdin.readLine();
                first = Integer.parseInt( inData);
 

                System.out.print("Enter last number: ");
                inData = stdin.readLine();
                last = Integer.parseInt( inData);
               

                System.out.println("The sum of numbers from "+first+" until "+last+" is "+Sum(first,last));

            }

          }

         

Before viewing the sample runs, lets trace a sample input:

                      Sum(first,last) = Sum(first,last-1) + Sum(last,last)

Sample Input: Sum(3,5)

Sum(3,5) = Sum(3,4) + Sum(5,5)                   [base case]

             = (Sum(3,3) + Sum(4,4)) + 5      [base case]

             = 3 + 4  + 5

             = 12

Sample Runs:

Run#1:

Enter first number: 1
Enter second number: 15
The sum of numbers from 1 until 15 is 120

Run#2:

Enter first number: 5
Enter second number: 7
The sum of numbers from 5 until 7 is 18

Run#2:
Enter first number: 1
Enter second number: 100
The sum of numbers from 1 until 100 is 5050

 

 

 

Example3

 

In this example, we want to write a method that implements the Power Function (recursively). Such that:

Given the base and the required exponent, the method will compute the base to the power of the exponent.

 

Thinking Recursively:

1- The base case

We know that any number to the power zero is equal to 1 (base case 1)

and that any number to the power one is equal to itself (base case 2)

2- The Formula

We know that a base to the power n is equal to the base multiplied by itself n times.

For example 43 = 4*4*4.

Therefore , we can say that our formula is

   

             Pow(base,n) = base*base*base*base*base.....n times

 

The following method implements the Power function.

import java.io.*;
class RecursivePower
{
   static double Power(double base,int exp)
   {
     if (exp == 0)         //base case 1
        return 1;

     else

        if (exp == 1)     //base case 2

           return base;
     else
        return base * Power(base,exp-1) ;
    }
    public static void main(String[] args) throws IOException
    {
     double number;
     int power;

     String inData;

     InputStreamReader inStream = new InputStreamReader( System.in );
     BufferedReader stdin = new BufferedReader( inStream);
 

     System.out.print("Enter base: ");
     inData = stdin.readLine();
     number = Double.parseDouble(inData);
 

     System.out.print("Enter power: ");
     inData = stdin.readLine();
     power = Integer.parseInt( inData);
 

     System.out.print(number+" to the power "+power+" is ");     

     System.out.println(Power(number,power));   
    }

}

Sample Runs:

Run#1:

Enter base: 2
Enter power: 3
2.0 to the power 3 is 8.0

Run#2:

Enter base: 4
Enter power: 2
4.0 to the power 2 is 16.0

Run#3:

Enter base: 2.5
Enter power: 4
2.5 to the power 4 is 39.0625

Run#4:

Enter base: 5
Enter power: 3
5.0 to the power 3 is 125.0

Run#5:

Enter base: 2
Enter power: 0
2.0 to the power 0 is 1.0

 

 

 

Example 4

In this example, we want to write a method that determines (recursively) whether a number is prime or not.

A prime number is a number that cannot be divided by any any integer other than one and itself.

For Example, 11 is a prime because its only divisors are 11 and 1.

Furthermore, 2 is the only even prime, the only divisors of 2 are 2 and 1.

 

Let's take a look first  at the non-recursive method for this:

                 

                         static boolean isPrime(int number)
                         {
                             boolean result= true;

                                if (number== 1) result = true;
                                else
                                if (number==0) result = false;

                             for (int i=2; i<number; i ++)

                             {
                                 if (number%i == 0)

                                   result = false;
                             }

                             return result;

                         }

Recursive Thinking:
1- The base case

We know that

1 is a a prime number

Therefore, this is the  base case.

2- The Formula

If we want to check whether a number is prime or not, we can do the following :

Check if it is divisible by any number before it until 2. If so, then it is not a prime. Otherwise it is prime.

For example, we would like to check if 5 is a prime number:

                    5 MOD 4 =1  

                    5 MOD 3 = 2 

                    5 MOD 2 = 1

Since, it is not divisible by any number before it then, it is a prime number.

What about 4? 

                    6 MOD 4 =1

                    6 MOD 3 =0                 

Since it is divisible by any number before it, then it is not a prime number.

 

Can you guess the formula ?

 

Take a look at the code:

import java.io.*;
public class RecursivePrime
{

  

public static boolean isPrime(int N)
   {

     if (N==1)
          return true;
     else
          return Prime(N,N-1);

   }

   public static boolean Prime(int X,int Y)

   {

      if ( Y == 1)
           return true;
      else
      if ( X%Y == 0)

           return false;
      else

           return Prime(X,Y-1);

   }

   public static void main(String[] args) throws IOException
   {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        int n;


        System.out.print("Please enter a positive number: ");
        n = Integer.parseInt(stdin.readLine());
 

        boolean result = isPrime(n);
 

        if (result)
           System.out.println("The number "+n+" is prime");
        else
           System.out.println("The number "+n+" is not prime");

    }

 } 

                          

Sample Runs:

Run#1:
Please enter a positive number: 2
The number 2 is prime

Run#2:
Please enter a positive number: 4
The number 4 is not prime

Run#3:

Please enter a positive number: 7
The number 7 is prime

Run#3:

Please enter a positive number: 9
The number 9 is not prime

 

 

 

Example5

 

A palindrome is a string of numbers or letters that is read the same forward as backward. There are trivial palindromes such as single letters ("I" ,"F", "L"), as well as longer palindromes such as the names "hanna" & "anna".

Other Examples of palindromes include:

"deed"

"racecar"

"level"

"madam"

"radar"

"num"

"eye"

"civic"

"pop"

 

In this example, we will write a method that determines whether the string entered by the user is a palindrome or not.

 

The Algorithm:

Let us take a look at the logic behind this problem. Let's use the string "racecar" as an example. 

 

r

a

c

e

c

a

r

0

1

2

3

4

5

6

 

 

As shown, this string consists of 7 letters. Written above is the position of each letter in the string starting from 0.

Now, we would like to compare the first and last letters. i.e. positions 0 and 6 in the string. They both contain the letter 'r' and therefore they are equal.

The next step would be comparing positions 1 and 5. They both contain the letter 'a' and therefore they are also equal.

Next, we will compare positions 3 and 5, to find that they both contain the letter 'c' and therefore they are equal.

Finally we are left with one letter in the 4th position 'e', so we stop.

Why did we stop?

There is nothing left to compare!

Conclusion:

The string is a palindrome.

 

Note that if one of the comparisons had not been equal then we would have stopped directly, knowing that the string cannot be a palindrome.

 

Think Recursively ( find the base case and the formula)

1-The base case

To find out what the base case is, we should recall why we stopped: we stopped when we were left with one letter. i.e. when there was nothing left to compare, or when the letters being compared where not equal.

These are the two base cases , but each one has a different return value.

If we stop because there is nothing left to compare, then the string is a palindrome, whereas if we stop because two letters are not equal then the string is not a palindrome.

2- The Formula

Basically, we want to compare the pairs of letters in the string. WE would like to compare those starting from the left side with those starting from the right side. Unless any of the pairs being compared are not equal , then the string is a palindrome.

 

The CheckPalindrome Method:

The method returns true if the string is a palindrome, and false otherwise.

It takes three parameters:

The first parameter is the string entered by the user.

The second is the starting position of the string ( we used zero)
The third is the position of the last character

 

The mechanism of the method

The method uses the charAt() method (of the class String) to compare the characters in the string.

 

The following code demonstrates the CheckPalindrome method:

import java.io.*;
public class Palindrome
{
     static boolean CheckPalindrome(String s, int leftSide, int rightSide)
     {
          if (rightSide <= leftSide)
               return true;
          else if (s.charAt(leftSide) != s.charAt(rightSide))
               return false;

          else
               return CheckPalindrome(s,leftSide+1,rightSide-1);

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

          String str;
          int n;         

 

          InputStreamReader inStream = new InputStreamReader( System.in );
          BufferedReader stdin = new BufferedReader( inStream );
         
          System.out.print("Please enter any string: ");
          str = stdin.readLine();

 

          int lastPosition = str.length()-1;

          boolean result = CheckPalindrome(str , 0, lastPosition);
 

          if (result)

            System.out.println("The string \""+str+"\" is a palindrome ");

          else         

            System.out.println("The string \""+str+"\" is not a palindrome ");


     }

}

Note that the following statement uses the method length() which is a method of the class String. This method returns the length of the given string.

                       

                          lastPosition = str.length()-1;

 

Also note that : The variable lastPosition represents the position of the last character in the string. Since java considers the first position in a string zero, therefore to get the position of the last character, we need to subtract 1 from the string's length.

For example, in a string of 8 characters, the position of the last character would be 7.

 

Sample Runs:
Run#1:

Please enter any string: smartrams
The string "smartrams" is a palindrome

Run#2:

Please enter any string: 11
The string "11" is a palindrome

Run#3:

Please enter any string: pop
The string "pop" is a palindrome

Run#4:

Please enter any string: xyz
The string "xyz" is not a palindrome

Run#5:

Please enter any string: xyayx
The string "xyayx" is a palindrome
 

 

Common Recursion Errors


Infinite Recursion

This occurs when the terminating condition is never met.

 

Example
 

static void recurseForever()

{

   recurseForever();

}

 

RenewSession