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)