Transcript chapter 3

Programming With Java
ICS201
Chapter 11
Recursion
University Of Ha’il
1
Programming With Java
ICS201
Definition





Recursion is a powerful concept that helps to simplify the
solution of complex problems.
Recursion means defining something in terms of itself.
This means that the solution of a problem is expressed in
terms of a similar problem but simpler.
That is, solving the simpler problem leads to the solution of
the original one.
Recursive solutions are shorter, easier to understand and
implement.
University Of Ha’il
2
Programming With Java
ICS201
Recursive Methods
o A recursive method is a method that calls itself directly
or indirectly.
o A recursive method has two major steps:
1.recursive step in which the method calls itself
2.base step which specifies a case with a known
solution
o The method should select one of two steps based on a
criteria:
Example:
recursive step: fact(n) = n * fact(n-1)
base step: fact(0) = 1
University Of Ha’il
3
Programming With Java
ICS201
Recursive Methods
o
The recursive step provides the repetition needed for
the
solution
and
the
base
step
provides
the
termination.
o
Executing recursive algorithms goes through two
phases:
1. Expansion in which the recursive step is applied
until hitting the base step
2. “Substitution” in which the solution is constructed
backwards starting with the base step
University Of Ha’il
4
Programming With Java
ICS201
Recursive Methods
•
•
•
fact(4)
recursive step: fact(n) = n * fact(n-1)
base step: fact(0) = 1
= 4 * fact(3)
= 4 * (3 * fact(2))
= 4 * (3 * (2 * fact(1)))
= 4 * (3 * (2 * (1 * fact(0))))
= 4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
=4*6
= 24
University Of Ha’il
5
Programming With Java
ICS201
Constructing Recursion
o To construct a recursive algorithm you have to find out:
1.Recursive step
2.Base step
o A selection structure is then used to determine which
step to take.
University Of Ha’il
6
Programming With Java
ICS201
General Algorithm
if (stopping condition) then
solve simple problem (base)
else
use recursion to solve smaller problem
combine solutions from smaller problem
University Of Ha’il
7
Programming With Java
ICS201
Benefits of Recursion
o Recursive methods are clearer, simpler, shorter, and
easier to understand.
o Recursive programs directly reflect the abstract solution
strategy (algorithm).
University Of Ha’il
8
Programming With Java
ICS201
When To Use Recursion
o The problem definition is recursive.
o The problem is simpler to solve recursively.
o When the produced results are used in the reverse order
of their creation.
University Of Ha’il
9
Programming With Java
ICS201
When Not To Use Recursion
o The recursion can be replaced with only a loop.
o Run -Time or space limitation.
University Of Ha’il
10
Programming With Java
ICS201
Infinite Recursion
o Recursion resembles loops in that it terminates based
on the condition.
o Missing the condition leads to infinite recursion.
o The recursive step must introduce a simpler version of
the problem leading to the base.
o Infinite recursion occurs as a result of not introducing
simpler problem.
University Of Ha’il
11
Programming With Java
ICS201
Recursion Removal
o Recursion can be removed by replacing the selection
structure with a loop
o If some data need to be stored for processing after the
end of the recursive step, a data structure is needed in
addition to the loop.
o The data structure vary from a simple string or an
array to a stack.
University Of Ha’il
12
Programming With Java
ICS201
Example (Recursion)
This method converts an integer number to its binary
equivalent.
Base step:
dec2bin(n) = n if n is 0 or 1
Recursive step:
dec2bin(n) = dec2bin (n/2) , (n mod 2)
Algorithm dec2bin(n):
If n < 2
else
Print n
dec2bin(n / 2)
Print n mod 2
University Of Ha’il
13
Programming With Java
ICS201
Example (Recursion)
class Method {
public static void dec2bin( int n){
if ( n < 2 )
System.out.print( n );
else {
dec2bin( n / 2 );
System.out.print( n % 2 );
}
}
}
class Dec2Bin{
public static void main(String [] arg){
}
dec2bin(i);
}
Output:
1010
int i=10;
University Of Ha’il
14
Programming With Java
ICS201
Example (iterative)
public static void dec2bin(int n){
String binary ="";
while ( n >= 1 ){
binary = n%2 + binary;
n /= 2;
}
System.out.print(binary);
}
University Of Ha’il
15
Programming With Java
ICS201
Example : Vertical Numbers
Output:
3
1
2
1
2
3
University Of Ha’il
16
Programming With Java
ICS201
The Recursive Method power
University Of Ha’il
17
Programming With Java
ICS201
Exercise
1. Write a recursive method to find the greatest common
divisor (GCD) of two integer n and m.
2. Write a recursive method to find Xn given the double X
and the integer n.
3. Consider a Boolean array b filled with Boolean values.
Write a recursive method boolean allTrue() that returns
true if all values are true and returns false otherwise.
University Of Ha’il
18