Transcript presentation (PowerPoint)

CSCD 300 Data Structures
Recursion
1
Proof by Induction
•
Introduction only - topic will be covered in detail in CS
320
•
Prove:
N
S
i=N(N+1)/2
i=1
•
Basis Step:
– show true for trivial case - here N = 1
•for N = 1 the sum is 1( 1 + 1 ) / 2 = 1
2
Proof by Induction
•
Inductive hypothesis:
– statement
is true for N = k
•
Inductive step:
•
if true for N = k show true for N = k + 1
–
S i=
i=1
k+1
i=1
(k + 1)
k
+Si
3
Proof by Induction
•
Inductive step:
S i = (k + 1) + k(k + 1) / 2 = (k + 1) (k + 2) /2
i=1
k+1
– so
by induction the statement is true for all k
4
Recursion
•
Math definition:
–
•
a solution to a problem that is defined in terms of
a simpler version of itself
Programming definition:
–
a function which calls itself
5
Recursion
•
Recursive definition of Sum of Integers:
public static int
Sum ( int n ) {
// assumes n is >= 1
if( n == 1)
return 1;
else
return Sum( n - 1 ) + n;
}
6
Factorial :
Mathematical Definition
•
Mathematical definition (recursive):
1 if N=1 or N=0
N! =
N * (N - 1)! if N > 1
7
Factorial:
Recursive Method
•
Recursive method:
public static int
factorial ( int n ) {
int temp;
System.out.println("Entering factorial: n = " + n);
if((n == 1)|| (n == 0))
temp = 1;
else
temp = n * factorial(n-1);
System.out.println("Leaving factorial: n = "+ n );
return temp;
}
Call:
System.out.println("Factorial(4):" + factorial(4));
8
Stack Frames
•
System Stack
– used
to control which function is currently active
and to reverse the order of function calls when
returning.
•
Stack Frame
–a
variable size piece of memory that is pushed onto
the system stack each time a function call is made.
9
Stack Frames
•
Stack Frame contains:
• space
for all local (automatic) variables
• the return address - the place in the program to
which execution will return when this function ends
• the return value from the function
• all parameters for a function (with actual parameter
values copied in
–The stack frame on top of the stack always
represents the function being executed at any point
in time - only the stack frame on top of the stack is
accessible at any time.
10
Factorial Trace
Ret Addr 2
N=1
Ret Value : 1
Ret Addr 2
N=2
Ret Value : 2
Ret Addr 2
N=3
Ret Value : 6
Ret Addr
1
N=4
Ret Value :24
Entering factorial N = 4
Entering factorial N = 3
Entering factorial N = 2
Entering factorial N = 1
Leaving factorial N = 1
Leaving factorial N = 2
Leaving factorial N = 3
Leaving factorial N = 4
11
Rules of Recursion
•
Always include a terminal case which does not
require recursion to calculate
•
Each recursive call should progress toward
the terminal case
•
Assume each recursive call works when
designing a recursive algorithm
12
Recursive Array Printing
public class ArrayPrintDriver {
public static void
printem( int[ ] array, int n, int last ) {
if(n <= last){
System.out.println( array[n]);
printem(array, n + 1, last);
2
}
}
public static void main( String args[] ) {
int[] values = new int[5];
for(int i = 0; i < 5 ; i++)
values[i] = i+1;
printem(values, 0, 4);
}
1
13
Array Printing Tracee
2
Ret Addr
last = 4 array = values
n=4
2
Ret Addr
last = 4 array = values
n=3
2
Ret Addr
last = 4 array = values
n=2
2
Ret Addr
last = 4 array = values
n=1
1
Ret Addr
last = 4 array = values
n=0
1
2
3
4
5
14
Multiple Recursion
•
•
Fibonacci Sequence: 0 1 1 2 3 5 8 13 21 44
– each number in sequence is the sum of the
previous two numbers (except the first two)
– Fibonacci number 0 = 0 Fibonacci number 1 =
1
– all other Fibonacci numbers are defined as
the sum of the previous two
15
Multiple Recursion
public static int
fib ( int n ) {
if ( n <= 1)
return n;
else
return Fib( n - 1) + Fib( n - 2 );
}
•
Problem: multiple calls are made to calculate
the same Fibonacci number
16
Problems with Recursion
•
Memory (stack) exhaustion:
–if
many stack frames are pushed - can run out of
space for stack
–if
each call allocates much memory - either
automatically or dynamically - heap exhaustion is
possible
•
Time:
–each
recursive call requires time to set up a new
stack frame, copy in actual parameter values and
transfer execution
17
Problems with Recursion
•
Any recursive algorithm can be rewritten using
iterative technique - it will be longer and more
likely to have problems but will run faster.
18
Recursive Binary Search
public static int
binarySearch(Comparable[ ] anArray, Comparable target, int left, int right) {
if(right < left)
return -1; // target not present
else {
int mid = (left + right) / 2;
if( target.compareTo(anArray[mid]) == 0)
return mid;
if( target.compareTo(anArray[mid]) < 0)
return binarySearch(anArray, target, left, mid -1);
else
return binarySearch(anArray, target, mid+1, right);
} // end else
}
19
Binary Search Trace
target = 3
Call 1 - left = 0 right = 9 mid = 4
[0] [1] [2] [3] [4] [5] [6]
10
5
9
7
3
2
0
[7]
13
[8]
15
[9]
20
Call 2 - left = 0 right = 3 mid = 1
[0] [1] [2] [3] [4] [5] [6]
10
5
9
7
3
2
0
[7]
13
[8]
15
[9]
20
Call 3 - left = 2 right = 3 mid = 2
[0] [1] [2] [3] [4] [5] [6]
10
5
9
7
3
2
0
[7]
13
[8]
15
[9]
20
return 2 (successful search)
20
Binary Search Trace 2
target = 1
Call 1 - left = 0 right = 9 mid = 4
[0] [1] [2] [3] [4] [5] [6]
10
5
9
7
3
2
0
Call 2 - left = 0 right = 3 mid = 1
[0] [1] [2] [3] [4] [5] [6]
10
5
9
7
3
2
0
Call 3 - left = 0 right = 0 mid = 0
[0] [1] [2] [3] [4] [5] [6]
10
5
9
7
3
2
0
[7]
13
[8]
15
[9]
20
[7]
13
[8]
15
[9]
20
[7]
13
[8]
15
[9]
20
Call 4 - left = 1 right = 0
Return -1 -- unsuccessful search
21
Binary Search Analysis
•
Worst case -target is not found:
–
Analysis proceeds in the same way as for the
iterative version only the number of passes is
replaced by the number of calls to binarySearch.
22
Towers of Hanoi
• Problem - disks of varying diameter are all on one peg (of
three) with the largest disks on the bottom and the smallest
on the top
• Goal - move all disks from peg A to peg C
• Rules - must move one disk at a time - can not place a larger
disk on a smaller disk
A
B
1
C
A
B
2
C
A
B
3
C
23
Towers of Hanoi - Stages
A
B
4
C
A
B
C
A
B
7
C
C
6
5
A
B
A
B
C
8
24
Towers of Hanoi - Algorithm
public static void
hanoi(int n, char source, char dest, char intermed)
{
if (n == 1)
System.out.println("move a disk from " + source
+ " to " + dest);
else
{
hanoi(n-1, source, intermed, dest);
System.out.println("move a disk from " + source 2
+ " to " + dest);
hanoi(n-1, intermed, dest, source);
}
3
}
original call: hanoi ( 3, 'A', 'C', 'B');
1
25
Towers of Hanoi - Analysis
•
How many calls are made to hanoi for n=3 ?
–
Each non-terminal call generates two more.
–
2n - 1 calls generated so f(n) = 2n - 1
–
Algorithm has O(2n) time complexity (exponential)
n=3
n=2
n=1
n=1
n=2
n=1
n=1
26