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 (subproblems),
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 subproblems:
1
divide the first segment into 8 equal pieces
2
divide the second segment into 8 equal pieces
How can we solve these 2 subproblems?
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(N1)*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 rethinking
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(N1)

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(row1)+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*(n1)*(n2) *..... *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 (n1)

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(n1));
}
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)+...+(last2)+(last1)+last
Recursively
Sum(first,last) = Sum(first,last1) + 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,b1)+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,last1) + 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 4^{3} =
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,exp1) ;
}
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 nonrecursive 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,N1);
}
public static boolean Prime(int
X,int Y)
{
if ( Y == 1)
return
true;
else
if ( X%Y == 0)
return false;
else
return Prime(X,Y1);
}
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)
1The 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,rightSide1);
}
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();
}