Transcript Recursion slides

Recursion
CS262
1
A common problem
Problem: Given a word, find its meaning
Algorithm: Look up the word in Webster’s Ninth New Collegiate
Dictionary
Problem: Given the word aardwolf, find its meaning
Answer: “a maned striped mammal of southern and eastern
Africa that resembles the related hyenas and feeds chiefly on
carrion”
Sub-problem: Given the word carrion, find its meaning
Answer:“dead and putrefying flesh”
CS262
2
Sub-sub-problem: Given the word putrefying, find
its meaning
Answer:“undergoing putrefaction”
Sub-sub-sub-problem: Given the word
putrefaction, find its meaning
Answer:“the decomposition of organic matter”
Final meaning: “a maned striped mammal of southern and
eastern Africa that resembles the related hyenas and feeds chiefly
on dead flesh that is undergoing decomposition”
CS262
3
A common problem-solving strategy
aardwolf
lookup
a maned striped mammal of southern and eastern Africa
that resembles the related hyenas and feeds chiefly on
carrion
lookup
dead flesh that is putrefying
lookup
undergoing putrefaction
lookup
decomposition
combine
undergoing decomposition
combine
combine
dead flesh that is undergoing decomposition
a maned striped mammal of southern and eastern Africa that resembles the
related hyenas and feeds chiefly on dead flesh that is undergoing
decomposition
CS262
4
Recursion: A common problem-solving strategy
Recursion occurs when an entity (e.g., a function or an algorithm) is
defined in terms of itself. In our example, the recursive entity is the
algorithm for looking up a word in a dictionary. Given a word:
1. Find the page containing the word
2. Read the definition of the word
3. If all words in the definition are understood, then stop. Otherwise, look
up each unknown word in the definition and combine their meaning with
the meaning of the known words to obtain the meaning of the original
word.
But wait, does it make sense to define something in terms of itself? How
does that help?
In our example, each time we look up a word, it is a different word. The
hope is that
eventually, the meaning of all the words in the definition will be known,
without need for another lookup.
CS262
5
Recursion works because the entity is defined in terms of
a variant of itself, and the variant gets easier and easier,
until the variant is so easy that its solution is obvious.
Recursion is a powerful problem-solving strategy that
computer programs can take advantage of.
CS262
6
The factorial function
• The factorial function is denoted by an
exclamation point. For example, the factorial
of 5 is denoted by 5!
• Definition of factorial:
For any positive integer n:
n!=n×(n−1)×(n−2)×...×3×2×1
0!=1
CS262
7
Two ways of implementation
Iteration:
Since n! = n x (n-1) x (n-2) x . . . x 2 x 1,
use a for loop.
Recursion:
Another way of defining factorial:
n! = n x (n-1)!
0! = 1.
We may want to define a method:
int factorial (n) {
return n x factorial(n-1);
}
CS262
8
Recursion considerations
• Why is this definition recursive?
• Write the Java implementation of this
function.
• Can this program go into an infinite loop?
• We need to ensure that there is a base case
where the recursion “bottoms out.”
• What is the base case in the factorial
example?
CS262
9
Factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))
= 3 * ( 2 * 1)
=3*2
=6
factorial
factorial
factorial
factorial
multiply
multiple
multiply
CS262
10
Example
• ComputeFactorial class
• NRComputeFactorial
CS262
11
Example of recursion with multiple base cases
• The Fibonacci numbers are computed as
follows:
fib(0)=0
fib(1)=1
For each n>1, fib(n) = fib(n−1) + fib(n−2)
• Run and study computeFabonacci.java
CS262
12
More examples
• Recursive print
– RecPrint.java and RePrintTest.java
• Towers of Hanoi:
– TowersOfHanoi.java
– TowersOfHanoi1.java
– TowersOfHanoi2.java
– Hanoe’s_Towers.jar
• Maze.java SearchMaze.java
CS262
13
More examples
• Fractals
– SierpinskiTriangle.java
– Koch snowflake – KochSnowflake.java
• Graphics
– TiledPictures.java
• Recursive Binary Search
• Palindrome
CS262
14