Transcript CS 201: Introduction to Programming With Java

CS203 Lecture 4
John Hurley
Cal State LA
Recursion
Recursion is the technique of breaking down a problem into
smaller instances of the same problem.
In programming, a recursive algorithm is one that directly or
indirectly invokes itself
direct recursion: methodA calls methodA
indirect recursion: methodA calls methodB and methodB calls methodA
Recursion
Recursion is used in many common algorithms. It is also
extremely important in functional programming, a longestablished paradigm (way of thinking about and practicing
programming) which is increasingly important today.
As you will learn in CS312, recursion is equivalent to iteration. In
other words, any problem you can solve with either of these two
techniques, you can also solve with the other. However:
a) many problems can be solved with simpler algorithms using recursion,
but
b) most programmers find iteration easier to think about
4
King of Hearts’ Algorithm
"Where shall I begin, please your majesty?" he asked.
"Begin at the beginning," the King said gravely, "and go on till you come to the end; then stop.
5
Recursive Algorithm
doSomething()
1. If you are finished, stop.
2. Otherwise
1.
2.
Solve part of the problem
Run this algorithm
Recursion
6
For example, we can define the operation goHome() this
way:
– Look around to see whether you are at home. If
you are, stop.
– Else
• Take one step toward home.
• goHome()
Recursion
Avoid infinite regression (and stack overflows) by
defining a condition that indicates that the recursion
has extended as far as it can, and that therefore causes
termination of the recursion. The instance of the
problem in which the condition is true is called the
base case.
8
Iterative (not Recursive) Factorial
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
Iterative algorithm
1. create new variable called running_total with a value of 1
2. begin loop
1.
2.
3.
4.
if n is 0, exit loop
set running_total to (running_total × n)
decrement n
repeat loop
3. return running_total
end
9
Recursive Factorial
Calculating the factorial of (a positive integer) n can be reduced to
multiplying n times the factorial of n-1.
function factorial:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. if n == 0, return 1
2. otherwise, return [ n × factorial(n-1) ]
Note that this recursive solution has a simpler relationship to the
actual definition of factorial than the iterative solution does
10
Recursive Factorial
public class Demo {
public static int factorialRecursive(int intIn){
if(intIn ==0) return 1;
return intIn * factorialRecursive(intIn -1);
}
public static void main(String[] args) {
int num = Integer.parseInt(JOptionPane.showInputDialog(null, "Please "
+ "enter the number whose factorial you would like to compute"));
JOptionPane.showMessageDialog(null, "The factorial of " + num + " is " +
factorialRecursive(num));
}
}
Stack Overflow
Each method call requires additional space on the call stack
to track the data values for the current instance of the
method
If the stack exceeds the memory available to it, a stack
overflow occurs
public class StackOverflowDemo {
int x;
public static void main(String[] args){
int x = 1;
StackOverflowDemo s = new StackOverflowDemo();
s.recurseToOverflow(x);
}
public void recurseToOverflow(int x){
System.out.println("instance " + x);
x = x + 1;
recurseToOverflow(x);
}
}
Stack Overflow
If you get a stack overflow error while doing your work in
this class, there is almost certainly a bug in your code that
involves an incorrect termination condition. Think until
you figure it out and fix it.
However, note that we run our programs inside Eclipse,
which decides how much space to allocate to the call
stack.
Euclid's Algorithm
Find the GCD of two positive integers this way:
Input Two positive integers, a and b.
Output The greatest common divisor, g, of a and b.
If a<b, exchange a and b.
Divide a by b and get the remainder, r. If r=0, report b as the GCD
of a and b.
Replace a by b and replace b by r. Return to the previous step.
http://www.math.rutgers.edu/~greenfie/gs2004/euclid.html
Euclid's Algorithm
// by Robert Sedgewick and Levin Wayne : http://introcs.cs.princeton.edu/java/23recursion/Euclid.java.html
// assumes p > q for simplicity
public class Euclid {
public static int gcd(int p, int q) {// recursive implementation
if (q == 0) return p;
else return gcd(q, p % q);
}
public static int gcd2(int p, int q) {// non-recursive implementation
while (q != 0) {
int temp = q;
q = p % q;
p = temp;
}
return p;
}
public static void main(String[] args) {
int p = Integer.parseInt(JOptionPane.showInputDialog(null, "Please enter the first integer"));
int q = Integer.parseInt(JOptionPane.showInputDialog(null, "Please enter the second integer"));
int d = gcd(p, q);
int d2 = gcd2(p, q);
Multiple Recursion
A recursive problem may have more than one base case
and/or more than one recursive call.
The definition of the Fibonacci numbers is recursive, and the
nth Fibonacci number can be found using a recursive function.
Fibonacci numbers: f(n) =
Multiple Recursion
public class FibonacciCalculator {
public static void main(String[] args){
FibonacciCalculator f = new FibonacciCalculator();
for(int counter = 0; counter < 10; counter++){
long fib = f.fibonacci(counter);
System.out.println("Fibonacci number No. " + counter + " = " + fib);
}
}
public static long fibonacci(long n) {
// https://www.inf.unibz.it/~calvanese/teaching/04-05-ip/lecture-notes/uni10/node23.html
if (n < 0) return -1; // F(n) is not defined when n is negative
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}
}
17
Recursion
Recursion can be used to process a list (or array of) values.
The termination condition occurs when there are no values left to
process; another way to put this is that the base case is the one in
which the number of values left to process is one.
Recursion
package demos;
import java.util.ArrayList;
import java.util.List;
//https:www.stackoverflow.com/questions/126756/examples-of-recursive-functions
public class RecursionExample {
public static void main(String[] args) {
String[] sleeplessArray = { "ant", "frog", "goose", "weasel", "child" };
List<String> sleeplessList = new ArrayList<String>();
for (String s : sleeplessArray)
sleeplessList.add(s);
RecursionExample r = new RecursionExample(sleeplessList);
}
public RecursionExample(List<String> animals){
System.out.print("There was a ");
tellStory(animals);
}
private void tellStory(List<String> sleeplessList) {
int last=sleeplessList.size() -1;
String animal = sleeplessList.get(last);
if(sleeplessList.size() == 1) System.out.println("little " + animal +" who went to sleep");
else {
System.out.println("little " + animal +
" who couldn't go to sleep, so his mother read him a story about a ");
sleeplessList.remove(last);
tellStory(sleeplessList);
}
System.out.println("so the little " + animal + " went to sleep" );
}
}
18
19
Recursion
Recursion can also be used to process a list of values and
produce a new list of processed values.
This is at the heart of functional programming, as you will learn
in CS332F. In the FP paradigm, neither the old list nor the
objects in the list change. We produce a new list containing
new values.
Functional languages like LISP, Haskell, and Scala are designed
to make this easy.
It is less straightforward in OOP, but the new version of Java
provides more support for this.
Recursion
package demos;
import java.util.ArrayList;
import java.util.List;
public class ListEx {
public static void main(String[] args) {
List<Integer> origList = new ArrayList<Integer>();
for (int counter = 1; counter <= 10; counter++) origList.add(counter);
ListEx r = new ListEx();
List<Integer> newList = r.squareList(origList, null);
for(Integer i: newList) System.out.print(i + " ");
}
private List<Integer> squareList(List<Integer> oldList, List<Integer> newList) {
int lastIndex = oldList.size() -1;
int base = oldList.get(lastIndex);
oldList.remove(lastIndex);
if(oldList.size() == 0) {
newList = new ArrayList<Integer>();
}
else newList = squareList(oldList, newList);
newList.add(base * base);
return newList;
}
}
20
21
Recursion
Here is the last example in Haskell:
Function definition:
squarelist :: Num a => [a] -> [a]
squarelist [] = []
squarelist (x:xs) = (x*x): squarelist xs
Function call:
squarelist[1..9]
22
Backtracking
Some algorithms involve following one path as far as it can go, then
backing up to the last point at which a different path could have
been chosen and then following that path
Depth-First Search (DFS) is a classic example. Start at the root of a
tree or graph and explore as far as possible along each branch
before backtracking.
23
Depth-First Search
Source of picture: https://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Depth-first-tree.svg/450px-Depth-first-tree.svg.png
File Listing
Consider the problem of listing all the files in a directory, including
those in all its subdirectories, etc. until every path has been
exhausted.
The natural way to approach this problem is to do it recursively
using Depth First Search:
List files in the current directory
Run this algorithm on each subdirectory, continuing as far as we can
go
File Listing
public class FileLister {
private static StringBuilder indentation = new StringBuilder();
public static void main(String args[]) {
String start = JOptionPane.showInputDialog(null,
"Please enter the starting directory");
getDirectoryContent(start);
}
private static void getDirectoryContent(String filePath) {
File currentDirOrFile = new File(filePath);
if (!currentDirOrFile.exists()) {
return;
} else if (currentDirOrFile.isFile()) {
System.out.println(indentation + currentDirOrFile.getName());
return;
} else {
System.out.println("\n" + indentation + "|_"
+ currentDirOrFile.getName());
indentation.append(" ");
String[] s = currentDirOrFile.list();
if (s != null) {
for (String currentFileOrDirName : currentDirOrFile.list()) {
getDirectoryContent(currentDirOrFile + "\\"
+ currentFileOrDirName);
}
}
Towers Of Hanoi
26
The Towers of Hanoi problem supposes that, at the beginning of time, a
group of monks in Hanoi were tasked with moving a set of 64 disks of
different sizes between three pegs, according to these rules:
No disk may ever be placed above a smaller disk
The starting position has all the disks, in descending order of size, stacked
on the first peg
The ending position has all the disks in the same order, stacked on the
third peg.
An optimal solution for n disks requires 2n-1 moves
264 = 18,446,744,073,709,551,616
There is a nice animation of a 4-disk version of the problem at
https://en.wikipedia.org/wiki/File:Tower_of_Hanoi_4.gif
27
Towers Of Hanoi
Recursive solution:
For any n > 1, the problem can be solved optimally in this way:
Solve the problem for n -1 disks, starting at the start post and ending
at the "extra" post.
The remaining disk will be the largest one. Move it to the finish
post.
Then solve the problem for the n-1 disks, moving from the "extra"
post to the finish post
The above procedure is applied recursively until n = 0
Before you try to understand the code from the book, try out the puzzle
online at
http://www.softschools.com/games/logic_games/tower_of_hanoi/
28
Towers Of Hanoi
The key to a Towers Of Hanoi solution is a recursive method like
this:
public void move(int disks, int from, int to) {
if (disks > 0) {
int other = 3 - from - to;
move(disks - 1, from, other);
towers[to].add(towers[from].remove());
move(disks - 1, other, to);
}
}
29
Tail Recursion
A tail-recursive method is one in which there is one recursive call
at the very end of the method, e.g. the examples above of
recursive factorial calculations and Euclid's algorithm.
In many programming languages, compilers can convert tail
recursion into iterative code, which is more efficient since it
does not create new instances on the call stack and since, in
many cases, it can avoid redundant calculations. This is called
Tail-Call Optimization, or TCO.
Java compilers may have this feature in the future, but not at the
current time.
30
Recursive Jokes
To understand recursion, read this sentence.
A truly greedy man is one who writes his will and
names himself as heir -- from Philogelos, the oldest known book of jokes,
compiled about 400 AD.
Function recurse()
1. If you are done with your program, stop
2. Otherwise,
A. Try to find the problem
B. Utter an obscenity
3. recurse()