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

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;

System.out.print("How many rows does the triangle currently have? ");
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;

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

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

}
}

Sample Runs:

Run#1:

The Factorial of 3 is 6

Run#2:

The Factorial of 4 is 24

Run#3:

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.*;
{
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;

System.out.print("Enter first number: ");
first = Integer.parseInt( inData);

System.out.print("Enter last number: ");
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;

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

System.out.print("Enter power: ");
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.

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
{
int n;

System.out.print("Please enter a positive number: ");

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"

"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;

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:

The string "smartrams" is a palindrome

Run#2:

The string "11" is a palindrome

Run#3:

The string "pop" is a palindrome

Run#4:

The string "xyz" is not a palindrome

Run#5:

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();

}  