PPTX - UF CISE
Download
Report
Transcript PPTX - UF CISE
1/ 22
COP 3503 FALL 2012
SHAYAN JAVED
LECTURE 17
Programming Fundamentals using Java
2/ 22
Recursion
3/ 22
Definition
Method where:
Solution to a problem depends on solutions of
smaller instances of the same problem.
4/ 22
Example: Merge Sort
i
0
1
2
3
4
5
A
55
19
100
45
87
33
Split
0
1
2
55
19
100
3
4
5
45
87
33
0
1
2
3
4
5
55
19
100
45
87
33
Now Sort and Merge
5/ 22
Recursive Function
A function which calls itself to solve a problem.
Alternative to iterative solutions
Most programming languages support recursion
Some
only support recursion (Functional languages)
6/ 22
Problems solved by Recursion
Mathematical problems (Factorial, Fibonacci
sequence, etc.)
Searching and sorting algorithms (binary search,
merge sort, etc.)
Traversing file systems
Traversing data structures (linked lists, trees)
Etc…
7/ 22
Defining a Recursive Function
1. When does the recursion stop?
Have
to stop at some point otherwise you’ll run into
problems
Also known as the “base case”
2. Repeat the process by calling the function again
8/ 22
Defining a Recursive Function
Example:
int recursiveMethod(parameters) {
if (baseCase)
return someValue;
else
return recursiveMethod(modifiedParameters);
}
9/ 22
Fibonacci sequence
A sequence of numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
How would you implement this recursively?
10/ 22
Fibonacci sequence
int fibonacci(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}
11/ 22
Fibonacci sequence
How would you implement this iteratively? (Using loops)
int fibonacci(int n) {
int fn1 = 0, fn2 = 1;
int prev;
for(int i = 0; i < num; i++) {
prev = fn1;
fn1 = fn2;
fn2 = fn2 + prev;
}
return fn1;
}
Let’s run both
12/ 22
Fibonacci sequence
Recursive version seems to be much slower.
Why?
What happens when a function call is made?
13/ 22
Function calls
When a method is called:
The method reference and arguments/parameters are
pushed onto the calling method’s operand stack
A new stack frame is created for the method which is
called. Contains variables, operand stack, etc. for it.
Stack frame is pushed onto the Java Stack.
When method is done, it is popped from the Java Stack.
14/ 22
Function calls
Java Stack Approximation after calling fibonacci(2):
fib(2)
Main
Main
1 is returned to Main
0
fib(0)
1
1
fib(1)
1
fib(2)
fib(2)
fib(2)
Main
Main
Main
Main
15/ 22
Function calls
Program counters have to be updated, local
variables, stacks, method references, etc.
So a lot of work is done when methods are called.
Imagine calling fibonacci(1000).
Results
in “stack overflow” (no available memory on
the call stack)
16/ 22
Recursion
Advantages:
Very
simple to write
Programs are short
Sometimes recursion is the only option
Disadvantages:
Extra
Slow
storage required
17/ 22
More Examples
Iterative version of Binary Search:
int binarySearch(int[] array, int key, int left, int right){
while (left <= right) {
int middle = (left + right)/2; // Compute mid point
if (key < array[mid]) {
right = mid-1;
// repeat search in bottom half
} else if (key > array[mid]) {
left = mid + 1; // Repeat search in top half
} else {
return mid;
// found!
}
}
return -1; // Not found
}
How would you implement recursively?
18/ 22
Binary Search
Identify base case first
When
do we stop?
When do you repeat?
19/ 22
Binary Search
int binarySearch(int[] array, int key, int left, int right) {
if (left > right)
// base case 1: not found
return -1;
int mid = (left + right)/2;
// Compute mid point
if (key == array[mid])
//
return middle;
else if (key < array[mid])
//
return binarySearch(array,
else
//
return binarySearch(array,
}
base case 2: found!
repeat search in upper half
key, left, mid-1);
lower half
key, mid, right);
20/ 22
File Systems
What happens when you run this command in
Linux?
rm –r *
Recursively (“-r”) goes through every file in the
directory and sub-directories and deletes it.
Has to use recursion
21/ 22
File Systems
How do you think the program “rm” is implemented?
Probably something like this (pseudocode):
function rm(directory):
File[] files = directory.getAllFiles();
for each file in files:
if (file is directory)
rm(file);
else
delete file;
22/ 22
Summary
Recursion is useful for writing simple programs.
Alternative to iterative solutions, but slower and
requires more space.
Some solutions require recursion (file directory
traversal)