Transcript Slide 1

APCS-AB: Java
Recursion in Java
December 12, 2005
week14
1
Check point
• Double Linked List - extra project grade
 Must turn in today
• MBCS - Chapter 1
 Installation
 Exercises
 Analysis Questions
week14
2
Scheme
• We started off the semester with Scheme… what
do you guys remember about the way that we
solved problems with Scheme?
 What was a list in Scheme? Was it really just the
LinkedList that you guys spent a week coding in Java?
• Scheme was functional, and we solved programs
recursively
 How can we apply that kind of problem-solving to
Java? Can using recursion improve our Java
problems? Why didn’t we think to use recursion with
the LinkedList in Java?
week14
3
Recursion in Java
• We can just as easily do recursion with Java, it’s just that
•
for some reason, with OO programming students tend to
default to thinking iteratively.
However, some problems can’t be easily solved
iteratively, but recursion gives you a very elegant
approach to solve these problems
 We’ll start with the “Classics” - some simple mathematical
problems and the Towers of Hanoi
• This will give you some easier problems on which to practice thinking
recursively again
 Then next semester we’ll move to using recursion to program
trees and faster sorting in order to show off recursion “in the real
world”
week14
4
Why use recursion?
• Sometimes a problem can be overwhelming to solve all
at once
 The nice thing about recursion is that it inherently chops a larger
problem into smaller ones
• Especially useful with lists and numbers which can be arbitrarily
large
• Sometimes it can be hard to prove that you have solved a
problem correctly…
 In math there’s proof by induction (which you may or may not
have seen before)
 So, recursion is just applying those same principles to problem
solving with computers
• Handle the simple cases directly
• Deal with the general case by breaking it down into operations
involving simpler cases (which by induction, we assume we can
handle)
week14
5
A brief introduction to
Proof by induction
• Prove 1+2+3+4+5+6+….+n = n(n21)
• Base Case: Show true for n = 1:
1(2)
1
1
2

• Induction Hypothesis (IHOP): Assume
claim istrue for n
• Induction Step -- Goal: Show true for n+1
1 2  ... n  (n 1) 
week14
(n 1)((n 1) 1)
2
6
The proof part
• Start with the original equation, which by
the IHOP we assume is true, and add
(n+1) to both sides:
week14
n(n  1)
1 2  ... n  (n  1) 
 (n  1)
2
n(n  1) 2(n  1)
1 2  ... n  (n  1) 

2
2
n 2  3n  2
1 2  ... n  (n  1) 
2
(n  1)(n  2)
1 2  ... n  (n  1) 
QED
2
7
Why use recursion?
• Provides an Elegant Solution
 Translates easily from thought [algorithm] to program
 Often allows for very short solutions
• Models some things in the real world much better than
alternatives
 number sequences
 math functions
 data structure definitions (eg linked lists)
• Remember how it came easily in Scheme??
 data structure manipulations (eg searching)
 language definitions
week14
8
Recursion: A Reminder
• Defining something in terms of itself
• For example – defined recursively, a list of numbers is:
 A (single number) - or
 A (number, list of numbers)
• 3
• 5, {4,5,6,7}
• Notice with recursion, you will ALWAYS have different
cases
 The Base definition(s)
 The General definition
week14
9
Recursion in Programming
• Recursive algorithm
 A solution that is expressed in terms of:
• a base case (1 or more)
• Simpler/smaller instances of the same algorithm
• Note: recursion depends on the fact that the algorithm
will eventually call a base case every time it is run
 The algorithm itself usually depends on applying the right base
case (note that you CAN have more than one)
 What else would happen if you didn’t call the base case?
• It would be infinite recursion… and your program would never stop
week14
10
Recursion in Math
• Many mathematical formulas can be expressed
recursively.
• Can you think of/remember any?
 Factorial
• 1! = 1  Fact(1) = 1
• N! = N*(N-1)!  Fact(n) = n*Fact(n-1)
• 5! = 5 * 4! = 5 * 4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1
 Fibonacci numbers
• Fib(0) = 0
• Fib(1) = 1
• Fib(n) = Fib(n-1) + Fib(n-2)
week14
11
Tracing an Example
public int sum(int num){
int result;
if(num == 1)
result = 1;
else
result = num + sum(num-1);
return result;
}
week14
12
How the trace works
returns 10
sum (4)
result = 4 + sum(3)
returns 6
sum (3)
result = 3 + sum(2)
returns 3
sum (2)
result = 2 + sum(1)
returns 1
sum (1)
result = 1
week14
13
How Recursion Works
• How does the computer keep everything straight:
 Specifically, how come local variables don't get trashed?
• The answer is that whenever a recursive method is
called, the following will occur:
 Its local variables are created from unused memory
• The new recursive call only sees these new memory locations
• The previous call still is pointing at the other memory locations
• This process repeats until you hit the base case
 When each method ends, its variables are deleted from
memory – the memory become unused again
week14
14
Dangers of Recursion
• Memory
 Think about how we described the inner workings of recursion
• The parameter(s) of your recursive method could have tens or
thousands of copies
• Execution Time
 Executing a method is far slower than running a typical iteration
of a loop
• Because you have to copy variables back and forth and do a
variety of other activities
• So iteration will usually be “faster” than recursion when executing
 So often you are trading “coding performance” for execution
performance
• You can use this fact to get an algorithm coded and tested, and
then go in to re-write it iteratively if you need better performance
week14
15
Searching and Sorting
• Searching is one of the most fundamental problems in
computer science, and one that is often used
 Can be implemented by a simple recursive algorithm
 One kind of search is particularly recursive: binary search
• Sorting is another task that comes up often in computer
science, and some of the best algorithms can be easily
implemented recursively
 Merge Sort
 Quick Sort
• We will look at these algorithms soon
week14
16
Lab Time: Simple Practice
• Using recursion write a method to:
 Calculate the factorial of a number
 Calculate Fibonacci Numbers of an input
 Calculate the first perfect square that is equal to or
smaller than a number
 Calculate x to the y power
 Determine if a number is prime
week14
17
Homework
• Write a program to determine and print the nth
line of Pascal’s triangle
 The first line of Pascal’s triangle is the single number 1
 The second line contains 2 numbers, each a 1
 The third line contains 3 numbers. Each of the
numbers contains the sum of the numbers (either 1 or
two) above it, so it would be 1 2 1
 Thus the fourth line would then be 1 3 3 1
• Hint: use an array to store the values on each
line
week14
18
APCS-AB: Java
Recursion in Java
December 13, 2005
week14
19
Checkpoint
• DoubleLinkedList - make sure its turned in
• Recursion Lab and Homework
 How was the lab? Did we get all the problems
 Show me your Pascal’s Triangle homework for
a grade
• Today:
 Lecture Featuring: Towers of Hanoi, Mazes
and N-Queens
 Lab: Towers, Mini-Project: N-Queens
week14
20
Introducing:
The Towers of Hanoi
Time for the fun to begin!
week14
21
Towers of Hanoi:
A Classic in CompSci
• The Towers of Hanoi puzzle was invented by the French
mathematician Edouard Lucas in 1883. There is a legend about an
Indian temple which contains a large room with three time-worn
posts in it surrounded by 64 golden discs. The priests of Brahma,
acting out the command of an ancient prophecy, have been moving
these disks, in accordance with the rules of the puzzle. According to
the legend, when the last move of the puzzle is completed, the world
will end. The puzzle is therefore also known as the Tower of Brahma
puzzle. It is not clear whether Lucas invented this legend or was
inspired by it. (From Wikipedia)
• Every computer science student encounters this puzzle at some
point - because it is one of the classic recursion and stack problems.
And the solution is quite elegant!
week14
22
Towers of Hanoi
• The puzzle is this: There are 3 pegs, resting on these pegs are 64
discs. None of the 64 discs are the same size; in fact, disc 1 is
slightly larger in diameter than disc 2, which is slightly larger than
disc 3, which is slightly larger than disc 4, etc. The initial
configuration of the puzzle has all 64 discs piled in order of size on
the first peg with the largest disc on the bottom. The goal is to
move all the discs onto the third peg. A large disc must never be
placed on a smaller disc and only one disc can be moved at a time.
• Should the world have ended if the legend is true? How long will it
take to move those 64 discs??
week14
23
Using Recursion
• Given that I just told you Towers of Hanoi can be
•
•
solved with recursion, how would you do it?
I have toys to help!
Remember:
 To formulate a recursive algorithm:
• Think about the base cases, the small cases where the
problem is simple enough to solve.
• Think about the general case, which you can solve if you can
solve the smaller cases.
 How would we would do this with the Towers? What is
the smallest case??
week14
24
“Backtracking” using
Recursion
• Backtracking is a way to solve hard “search”
problems
 Go down one path towards a solution, but undo steps
if you “take a wrong turn”
• Two classics
 Solving Mazes
 Placing N-Queens on an N x N board
• So how do we do this? And where can we use
recursion? How do we backtrack with recursion?
week14
25
Mazes with recursion are
aMAZE-ing
• Let’s say we had a maze that was represented by a 2D
int array with 1 indicating a “clear” path and 0 a “blocked”
path - How could we use recursion to help solve a maze
like:
1110110001111
1011101111001
0000101010100
1110111010111
1010000111001
1011111101111
1000000000000
1111111111111
week14
Top-left is entry point
Bottom-right is exit point
You can only move down, right, up and left
26
Maze Code (Class Handout)
• How does this work? What happens?
 For each “starting” position, we are looking for a solution to the end. (Each
problem is a smaller subset of the original problem)
• When we have a valid move, we try it (and mark it tried so that we
don’t retrace steps later)
• We stop recursion for a given path for one of 3 different cases:
 If the move is invalid because it is out of bounds
 If the move is invalid because it has been tried before
 If we have reached our final location (bottom-right)
week14
27
The Solution
• We “backtrack” each time we try a path that doesn’t find a solution (to
the bottom-right corner)
• All the 3’s in the output are places we tried that we had to backtrack from
• If we find a solution, the grid entry is changed to 7 (the first 7 set is
the bottom right corner)
7770110001111
3077707771001
0000707070300
7770777070333
7070000773003
7077777703333
7000000000000
7777777777777
• Do we understand how this works??
week14
28
N-Queens
• N-Queens on an nxn board
 How can we put n queens on an board so that
no two queens attack each other?
• No Queens are on the same:
 Row
 Column
 Diagonal
week14
29
Queens Demo
week14
30
Lab & Mini-project
• Lab: Towers of Hanoi
 Work on in in class today and tomorrow
• Mini-project: 8-Queens - for Thursday
 Solve it for the 8 x 8 case, using code
provided
 The general case is the same, but 8 x 8
definitely has a solution
week14
31