Transcript Recursion

Recursion
Chapter 11
How it works
“A recursive computation solves a
problem by using the solution of the
same problem with simpler inputs”
Big Java, Horstman, p. 669
“For recursion to terminate, there
must be special cases for the simplest
inputs.” Big Java, Horstman, p. 670
An example
public class Triangle
{
private int aWidth;
public Triangle (int width)
{
aWidth = width;
}
public int getArea()
{
} //Big Java, Horstman, p. 670-71
An example
public class Triangle
{
private int aWidth;
public Triangle (int width)
{
aWidth = width;
}
public int getArea()
{
if (width <= 0)
return 0;
if (width ==1)
return 1;
Triangle smallerTriangle = new Triangle(width -1);
int smaller Area = smallerTriangle.getArea();
return smallerArea + width;
}
Common Error
Infinite recursion!!!!
Key requirements for Recursion
Every recursive call must simplify the
computation in some way
There must be special case(s) to
handle the simplest computations
directly.
Alternative to recursion
Iteration
Why one or the other?
“In many cases a recursive solution is
easier to understand and implement
correctly than an iterative solution.
Occasionally, a recursive solution runs
much slower than its iterative
counterpart. However, in most cases, the
recursive solution is only slightly slower.”
Big Java, Horstman, p. 694
Recursive Definitions
“ A definition in which the item being
defined appears as part of the definition is
called an inductive definition or a
recursive definition…
Recursive definitions have two parts:
A basis, where some simple cases of the item
being defined are explicitly given
An inductive or recursive step, where new
cases of the item being defined are given in
terms of previous cases” Mathematical Structures for
Computer Science, Gersting, pp.120-121
Example of a Sequence
A sequence S is a list of objects that
are enumerated (listed) in some
order; there is a first such object, then
a second, and so on. S(k) denotes
the kth object in the sequence. A
sequence is defined recursively by
explicitly naming the first value (or the
first few values) in the sequence and
then defining later values in the
sequence in terms of earlier values.
Explicit Examples –
recursively defined sequences
Example 1
S(1) = 2
S(n) = 2S(n-1) for n>= 2
Example 2
T(1) = 1
T(n) = T(n-1) + 3 for n >= 2
Example 3
F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2) for n > 2
Explicit Examples
recursively defined operations
Example 4
a0 = 1
an = (an-1)a for n >= 1
Example 5
m(1) = m
m(n) = m(n-1) + m for n >= 2
Code Example
Example 6
public int factorial(int n)
{
int value;
if ((n == 0) || (n == 1))
value = 1;
else
value = n*factorial(n-1);
return value;
}
Computer Behavior
When a method is called, an activation
record (or invocation record) is created
Method calls/returns happen in a last-infirst-out manner
Activation Records Contain:
Local variables and their values
The location (in the caller) of the function call
Execution status (e.g., processor registers) of
the current module
Other things
Card technique for understanding recursion
Use "Cards" for Activation Records:
Each card contains the local variables
and their values
The location (in the caller) of the method
call
Tracing Execution:
Add a "card" to the top of a stack when a
method is called and remove a "card"
when the method returns
Designing Recursive Algorithms
An Example - Print the Digits of a
Number:
Easy Case - The number consists of 1
digit
Reducing Difficult Cases - Integer
division by 10
Implementation –
Print the Digits of a Number:
public void printBase10(int n)
{
if (n >= 10)
printBase10(n/10);
System.out.print(n%10);
}