Java程序辅导

Friday 4/8
Announcements:
 Homework 8 due Today
 Quiz 3 next Wednesday
 Towers of Hanoi - Recursion
For Next Time
 Read Sections 5.3 - Binary Search 
 Read Sections 5.6 - Backtrack Search     or 6.1-6.2 - Trees
Today
 Questions on Lab 7 or Homework 8
 Recursion Examples
 In-class Exercise
Recursion – Chapter 5
 Recursion is a technique for solving problems where a method 
calls itself
 Whenever we can define a problem using a smaller instance 
of the same problem, we can use recursion
 Examples
 sum(n): sum(n) = n + (n-1) + … + 2 + 1
 factorial(n): n! = n * (n-1) * … * 2 * 1
 fibonacci(n): fib(n) = fib(n-1) + fib(n-2)
print a sentence in reverse order
 gcd(m,n)
efficiently search a sorted array
 solve towers of Hanoi
Writing Recursive Methods
 The key to solving a problem recursively
Base case
Recursive formula 
• smaller instances of the problem that can be used to solve 
the original problem 
 Recursive methods have this structure
If (base case) 
return value
else
recursive call with smaller instance of problem
Recursion:  sum(n)
sum(n) = 
1                             if  n=1      (base case)
n + sum(n-1)           if  n>1
public static int sum(int n) {
if (n==1)
return 1;
else
return n + sum(n-1) ;
}
sum(n) = n + (n-1) + … + 2 + 1
sum(n) = n +    sum(n-1)
Let’s try it!!
Eclipse
PracticeRecursion
Tracing Recursion
 Activation Frame (Activation Record/Execution Frame) 
Created when the method is called and contains
Storage for formal parameter (method arguments)
Storage for local variables
Return address of calling method
 Recursion Tree
Used to trace the execution of a recursive method
Helpful when there is more than one recursive call
• fib(n) = fib(n-1) + fib(n-2)
sum(4)    Activation Frames
sum(4)
n=4
return 4 + sum (3)  
sum(3)
n=3
return 3 + sum (2)  
sum(2)
n=2
return 2 + sum (1)  
sum(1)
n=1
return 1
1
3
6
10
Recursion
fib0 fib1 fib2 fib3 fib4 fib5 fib6 fib7 …
0      1     1     2      3    5     8     13
fib(n) = fib(n-1) + fib(n-2)
fib(n) = 
0                                       if  n=0  (base case)
fib(n-1) + fib(n-2)          if  n>1
public static int fib(int n) {
if (n==0)
return 0;
else if (n==1)
return 1;
else
return fib(n-1) + fib(n-2);
}
1                                       if  n=1  (base case)
Fibonacci Numbers
fib(n) = fib(n-1) + fib(n-2)
fib (5)
return 3+2
fib (4)
return 2+1
fib (1)
return 1
fib (0)
return 0
fib (1)
return 1
fib (2)
return 1+0
fib (3)
return 1+1
fib (2)
return 1+0
fib (1)
return 1
fib (0)
return 0
fib (3)
return 1+1
…
Recursive Example: scanReverse
 Write a method scanRev(scan) that has input scan a Scanner and 
prints all the tokens in the Scanner in reverse order
Example: scan has : a b c d prints: d c b a
Base case: scan is empty
Note: scanRev(a b c d) =  d c b a
= scanRev (b c d)  print(a)
return                if scan is empty
token = scan.next()  if scan not empty
scanRev(scan)
print(token + “ “)
recursive formula
scanRev(scan) =
In-class Exercise
RecursionPractice.java