Transcript Powerpoint - MHS Comp Sci

Recursion
Purpose: There are situations
where iterative algorithms become
too complicated and a more elegant
solution would be helpful. You can
design an algorithm where it
performs a simple task and that task
it repeatedly called.
This process is called recursion.
1
Resources:
Java Essentials Chapter 17 p.667
Java Essentials Study Guide Chapter
14 p.221
Barrons AP Java Chapter 17 p.219
2
Handouts:



Fibonacci.java
Factorial.java
combo.java
M/C Questions
3
Recursive Functions:
Functions whose code includes calls
to itself
Possible because successive function
calls create instances of the “stateful”
properties of the function
A frame on the stack
The function code is shared
4
Recursive Functions:
The system implements a function
call the same way : whether the
function calls itself or another
function.
5
3 Rules:
find out how to take just 1 step
break each journey into 1 step
plus a smaller journey (work
towards the base case)
know when to stop --- BASE
CASE
6
Base Case:
The “regular line”
The lowest level where no
recursive calls are made
The place where no recursive calls
are made
7
Recursive Case:
A repeat command
8
Recursion & Iteration:
Iteration explicitly uses a
repetition structure
(loops)
Recursion achieves repetition
through repeated function calls
9
Recursion & Iteration...
Both involve a termination test:
Iteration ends when loop fails
Recursion ends when a base case is
recognized ( a simpler version of the
original problem is produced until the
base case is reached)
Both can occur indefinitely if not
designed correctly
10
When NOT to use Recursion:
functions declaring large local
arrays
functions that manipulate static
vars, global vars or arrays
if performance is vital
when dealing with linear
structures and processes (simple
iterations are best)
11
Recursion Drawbacks:
It repeatedly invokes function calls
onto the stack
Expensive in CPU time and
memory
12
When Recursion is Best Used:
Used best when it significantly
simplifies the code without
excessive performance loss.
Useful for dealing with nested
structures or branching processes
Used in traversing tree structures
13
Sample Problem:
A recursive algorithm for painting a square.
Given a square
If the length is less than 2 ft, stop
Divide the square into 4 equal size
squares
Paint 1 of these small squares
Repeat from the top for each of
the 3 unpainted squares
Square of 16 feet (256 square ft)
14
Sample Problem…
How Many Squares Created &
Painted...
In the 1st pass ?
In the 2nd pass ?
In the 3rd pass ?
In the 4th pass ?
What is the TOTAL SQUARES
Painted?
Take some time now to try this...
15
Sample Problem:
1st pass, four 8” squares 1p 3 up
2nd , 12 4” squares 3p 9 up
3rd, 36 2” squares, 9p 27up
4th, 108 1” squares, 27p, 81up
total painted = 1+ 3 + 9 + 27 = 40
16
SIGMA Example
Use the following function shell
to code for a recursive algorithm
that SUMS INTEGERS FROM 1 to
N
17
SIGMA Example
Int Sigma (int n)
{
}
18
Int Sigma (int n)
{
if (n <= 1)
return n;
else
return n + Sigma(n-1);
}
19
TPS:
Convert and Print a Decimal number
(100) to a binary number (base 2)
100 / 2 = 50 remainder 0
50 / 2 = 25 remainder 0
25 / 2 = 12 remainder 1
12 / 2 = 6 remainder 0
6 / 2 = 3 remainder 0
3 / 2= 1 remainder 1
1 / 2 = 0 remainder 1
20
Reading remainders in reverse order
gives result: 1100100 the binary
for 100
Write a Recursive solution:
Identify the first step
Break down step into a smaller
version
Know when to stop --- the base case
(quotient <= 0)
The last remainder must be the first
printed
21
Here is the Shell Code:
public static void convertToBinary(int dec)
{
}
22
ANS: Java Essentials Study Guide Chapter 14
p.222
public static void convertToBinary(int dec)
{
int quotient = decimalNum / 2;
int remainder = decimalNum % 2;
if (quotient > 0)
{
convertToBinary(quotient);
// smaller version
}
System.out.println(remainder);
// base case
}
23
FIBONACCI Example (handout)
COMBO Example (handout)
REVERSE A SENTENCE
24
EFFICIENCY
“a measure of the runtime usage
of computational processes”
Select an instruction in the
algorithm that executes
more/less based on the size of
the data (this process dominates
the work)
25
EFFICIENCY...
Linear Behavior -- Number of
instructions executed
INCREASES PROPORTIONAL to
the size of the data
26
EFFICIENCY...
Quadratic Behavior -- Number of
instructions executed
INCREASES PROPORTIONAL to
the size of the data SQUARED
Least Efficient of these
27
EFFICIENCY...
Logarithmic Behavior -- LOG 2 N
MOST Efficient
28
EFFICIENCY… Illustration
Data
Log2
1
10
100
1
4
7
1,000 10
10,000 14
Linear
N log N
Quadratic
1
10
100
1
40
700
1
100
10,000
1,000 10,000 1,000,000
10,000 140,000 100M
29
Efficiency…
Exponential Growth O(a^n)
Recursive functions, like FIBONACCI, have
an exponential order of growth
Lets Run Fibonacci Recursively…
..\recursion programs\fibonacci.exe
30
Linked Lists as Recursive Data
Structures
Given A Simple Structure, how
Can we design a recursive
function that traverses a linked
list ?
(This will be discussed during
our lecture on Linked Lists)
31
TPS (OPTIONAL):
Permutations of a
String (Java Essentials ch 17 p.672 - 676)
Design a class that lists all the permutations
of a string
For example, the string “eat” has 6
permutations:
eat
eta
aet
ate
tea
tae
Use the text for approach and code solution
32
TPS (OPTIONAL): GasPump
(Java essentials Study Guide Vhapter
14 p.223-224)
Write a recursive class that simulates
the spinning of the digits on a gas
pump
Use the text for approach and code
solution
33
Tips for the AP Exam:
The AP Exam includes M/C questions
that give a recursive algorithm and
then ask about that algorithm
You will need to be able to TRACE
through a recursive process to obtain
the answer
34
Tips for the AP Exam:
Never use a while statement when
an if statement should be used to
check for a base case in a recursive
algorithm
Avoid infinite recursion by coding for
a base case that WILL be reached
35
Tips for the AP Exam:
Unless the solution requires you to
write a recursive solution OR the
problem is stated in a recursive
nature, code solutions ITERATIVLY
36
Tips for the AP Exam:
When there is ONE recursive call
from “return”, use the STACK
METHOD to help you resolve the
code
Example, Factorial
37
Tips for the AP Exam:
When there are TWO recursive calls
from “return”, use the BINARY TREE
METHOD to help you resolve the
code
Example, Combo & Fibonacci
38
LAB:
Factorial
Making Change
Multiple Choice Questions
39