Advanced Programming Techniques (2011, 2013)
4. Iteration and Recursion
51
Iteration
Iteration is the process of repeating a block of statements in a computer program by using a repetition control structure, also known as a loop. Here is a simple example of iteration written in Java that computes n factorial (n!).
Example 1
/** Iteratively computes n factorial (n!)
* which is n * (n-1) * (n-2) * ... 1 */
public static long factorial(int n) {
long fact = n;
while (--n > 1) {
fact *= n;
}
return fact;
}
|
Desk Check |
|
|
n |
fact |
|
4 |
|
Recursion
Recursion is the process of repeating a block of statements in a computer program by using a recursive function. A recursive function is a function that calls itself either directly or indirectly. A function F calls itself indirectly by calling function G which calls function F. A recursive algorithm solves a problem by repeatedly dividing it into smaller sub-problems until reaching the simpliest sub-problem and then solves that simpliest problem. All recursive algorithms must have three parts:
1. A base case which is the simpliest sub-problem and when the recursion will stop
2. Code to work toward the base case by dividing the problem into sub-problems
3. One or more recursive function calls
Parts 2 and 3 are often combined into a single line of code. As a student, the first example of a recursive function that I saw was one that computed n factorial as shown in example 2.
52
Example 2
/** Recursively computes n factorial (n!)
* which is n * (n-1) * (n-2) * ... 1 */
public static long factorial(int n) {
if (n > 1) {
return n * factorial(n - 1);
}
return 1;
}
|
Desk Check |
||
|
Function |
Variables |
|
|
factorial |
n |
return |
|
4 |
||
|
factorial |
n |
return |
|
factorial |
n |
return |
|
factorial |
n |
return |
Notice in example 2 the three parts of a recursive algorithm. The base case is when n == 1, and the solution to 1 factorial is simply 1. Working toward the base case is done by splitting n factorial into n * (n − 1 factorial). Working toward the base case and the recursive call to the factorial function are combined into one line of code. Figure 20 shows the order in which the recursive factorial function calls itself and returns from those calls.
Figure 20: Function calls and returns for the recursive factorial function.
As a student this example made no sense to me because I realized that n factorial could be easily computed using iteration as shown in example 1. Recursion began to make sense to me when I learned that
1. Recursion comes to computer science from mathematics, and mathematicians define some mathematical functions, such as the Fibonacci series, in a recursive form.
2. Some programming languages such as Erlang, ProLog, and Haskell, don’t include iteration, because the inventors of those languages believed that iteration was error prone and that recursive solutions revealed the intrinsic structure of a problem.
3. There are many programming problems more complex than the simple recursive examples shown in text books (such as n factorial) that are elegantly solved using recursion.
53
Advantages of Recursion
Recursion has several advantages over iteration, including
1. If a computing problem can be broken into smaller self-similar problems, a recursive solution is almost always shorter and more elegant than an iterative solution.
2. A recursive function uses existing, well-understood, and tested functionality, namely the system stack, as part of its solution instead of requiring that another stack module be written.
3. It is sometimes necessary to prove that a computing solution is correct. Proving correctness is easier for a recursive solution than an iterative solution because recursion and proof by induction are closely related.
Disadvantages of Recursion
The disadvantages of using recursion include the following.
1. Using recursion means many function calls. In many programming languages, a fuction call is relatively slow compared to other operations. In languages that don’t include iteration, the language compiler or interpreter will transform some recursive functions into iterative ones to lower the number of function calls. If a programmer writes a recursive function in a language that doesn’t include this optimization, that function will likely be much slower than an iterative function that solves the same problem.
2. Recursion can be hard to learn and understand especially for someone that has already learned iteration.
3. A recursive function may use all the memory in the system stack which will cause the program to crash. Try this simple Java program.
Example 3
public class Crash {
public static void main(String[] args) {
fillTheStack(1);
}
/** Recursively calls itself until the
* system call stack fills and the program
* crashes with a StackOverflowError. */
public static void fillTheStack(int frameNumber) {
System.out.println(frameNumber);
System.out.flush();
fillTheStack(frameNumber + 1);
}
}
How many numbers did the program print on your computer before filling the stack and crashing? My computer produced 11415, and then the program crashed. Of course, if the function fillTheStack declared local variables besides its one parameter, each function call would require a larger stack frame, and the program would produce fewer numbers before crashi
54
Tail Recursion
Tail recursion is a special form of recursion where a recursive function calls itself as its final action. Here is an iterative function to compute the greatest common divisor (gcd) of two integers and the same functionality written as a tail recursive function.
Example 4
/** Iteratively computes the greatest
* common divisor of two integers. */
public static long gcd(long x, long y) {
// Loop until the greatest common divisor is found.
long r; // Holds the remainder
do {
r = x % y;
x = y;
y = r;
} while (r != 0);
return x;
}
|
Desk Check |
||
|
x |
y |
r |
|
472 |
24 |
|
Example 5
/** Recursively computes the greatest
* common divisor of two integers. */
public static long gcd(long x, long y) {
long rem = x % y;
if (rem == 0) {
return y;
}
return gcd(y, rem);
}
|
Desk Check |
||||
|
Function |
Variables |
|||
|
gcd |
x |
y |
rem |
return |
|
472 |
24 |
|||
|
gcd |
x |
y |
rem |
return |
|
gcd |
x |
y |
rem |
return |
Figure 21: Function calls and returns for the recursive gcd function.
Figure 21 shows the order in which the recursive gcd function calls itself and returns from those calls. Many programming languages automatically convert a tail call to a goto statement or an assembly language JUMP instruction which makes a tail recursive function execute as quickly as an iterative function. From figure 21 it is easy to see why a compiler can optimize a tail recursive call into a JUMP instruction. Notice that every return shown in figure 21 returns the same value, which is the value returned by the last call to the gcd function.
55
Converting Recursion to Iteration
Programming languages without recursion and with only iteration for repeating statements have been proven to be Turing complete. The same is true for programming languages that have no iterative control structures and use only recursion for repetition. This means that both types of languages can solve the same types of computing problems. Or in other words, any recursive solution can be converted to an iterative solution and vice versa.
Some programming languages don’t include recursion. Also, some companies, notably defense companies, don’t allow their software developers to use recursion because of the possibility of a recursive function overflowing its call stack. Imagine if one of the programs in an F-35 fighter jet overflowed its call stack and crashed while the plane was flying. This might cause the plane to launch its weapons prematurely or cause the plane to crash. Programmers working in these environments must convert recursive functions to iterative ones.
All tail recursive functions can be converted into iterative functions that use a simple loop and vice versa. Many recursive functions that are not tail recursive can be converted to tail recursive functions by adding accumulator parameters. All other recursive functions can be converted to iterative functions by writing and using a stack in place of the system call stack.
Tail Recursion to Iteration
All tail recursive functions can be converted into iterative functions that use a simple loop and vice versa. Consider this simple tail recursive function that prints integers backwards from n down to 1.
Example 6
/** Recursively prints the numbers
* backwards from n down to 1. */
public static void countDown(int n) {
if (n < 1) {
return;
}
if (n > 0) {
System.out.println(n);
countDownR(n - 1);
}
}
Notice how easily it is converted to an iterative function with a simple loop.
Example 7
/** Iteratively prints the numbers
* backwards from n down to 1. */
public static void countDown(int n) {
for (; n > 0; n--) {
System.out.println(n);
}
}
56
Non-Tail Recursion to Tail Recursion
Any tail recursive function can be converted to an iterative function and vice versa. So what can a programmer do with a non-tail recursive function? First convert it to a tail recursive function then convert that to an iterative function. Here is a non-tail recursive function that computes the sum of the numbers in an array. It is not tail recursive because the call from the sumR function to itself is not the last action in the sumR function. After the call returns, the last action is addition.
Example 8
public static double sum(double[] a) {
return sumR(a, 0);
}
/** Recursively computes the sum of the numbers in a. */
private static double sumR(double[] a, int i) {
if (i == a.length) {
return 0;
}
return a[i] + sumR(a, i + 1);
}
|
Desk Check |
|||||
|
Function |
Variables |
||||
|
sum |
a |
return |
|||
|
6.5 |
7.1 |
6.9 |
|||
|
[0] |
[1] |
[2] |
|||
|
sumR |
i |
return |
|||
|
sumR |
i |
return |
|||
|
sumR |
i |
return |
|||
|
sumR |
i |
return |
|||
This non-tail recursive function can be converted to a tail recursive function by adding an accumulator parameter (the parameter s in the sumR function below) and moving the addition into the arguments of the recursive call to sumR.
Example 9
public static double sum(double[] a) {
return sumR(0, a, 0);
}
/** Recursively computes the sum of the numbers in a. */
private static double sumR(double s, double[] a, int i) {
if (i == a.length) {
return s;
}
return sumR(s + a[i], a, i + 1);
}
|
Desk Check |
||||||
|
Function |
Variables |
|||||
|
sum |
a |
return |
||||
|
6.5 |
7.1 |
6.9 |
||||
|
[0] |
[1] |
[2] |
||||
|
sumR |
s |
i |
return |
|||
|
sumR |
s |
i |
return |
|||
|
sumR |
s |
i |
return |
|||
|
sumR |
s |
i |
return |
|||
57
This tail recursive function is easily converted to iteration.
Example 10
/** Iteratively computes the sum of the numbers in a. */
public static double sum(double[] a) {
double sum = 0;
for (int i = 0; i < a.length; ++i) {
sum += a[i];
}
return sum;
}
The recursive factorial function listed at the beginning of this chapter is another example of a non-tail recursive function that is easily converted to tail recursion by adding a helper function and an accumulator parameter and moving the multiplication into the arguments to the recursive call.
Example 11
public static long factorial(int n) {
return factorialR(1, n);
}
/** Recursively computes n factorial (n!)
* which is n * (n-1) * (n-2) * ... 1 */
private static long factorialR(long f, int n) {
if (n == 1) {
return f;
}
return factorialR(f * n, n - 1);
}
|
Desk Check |
|||
|
Function |
Variables |
||
|
factorial |
n |
return |
|
|
4 |
|||
|
factorialR |
f |
n |
return |
|
factorialR |
f |
n |
return |
|
factorialR |
f |
n |
return |
|
factorialR |
f |
n |
return |
Converting Other Recursion to Iteration
Some non-tail recursive functions, including recursive functions that call themselves from multiple locations, cannot be converted to tail recursion. The straight forward way, although not always the best way, to convert such a recursive function to an iterative one, is for a programmer to create and use his own stack in place of the system call stack. Then the code in the iterative function must simulate calling and returning from the function by pushing and popping variables on the stack.
58
Binary Tree
|
Node |
|
–left : Node |
|
+Node(data : String[]) |
|
BinTree |
|
–root : Node |
|
+BinTree() |
Figure 22: A UML class diagram for a binary search tree.
Consider a binary search tree that stores a string at each node as shown in the UML class diagram in Figure 22. Figure 23 shows an instance of this binary search tree that has a name stored at each node. Any function that traverses the entire tree can be written as a recursive or iterative function. Here is a recursive Java function that traverses the tree and returns the length of the longest string that is stored within the tree.
Figure 23: A binary search tree with a name stored at each node.
Example 12
/** Returns the length of the longest
* String stored in this binary tree. */
public int maxLen() {
return maxLenR(root, 0);
}
/** Recursively finds the length of the
* longest String stored in this binary tree. */
private int maxLenR(Node curr, int max) {
if (curr != null) {
int len = curr.data.length();
if (len > max) {
max = len;
}
max = maxLenR(curr.left, max);
max = maxLenR(curr.right, max);
}
return max;
}
|
Desk Check |
|||||||||||||||||||
|
Function |
Variables |
||||||||||||||||||
|
maxLen |
return |
||||||||||||||||||
|
maxLenR |
curr |
max |
len |
||||||||||||||||
|
maxLenR |
curr |
max |
len |
curr |
max |
len |
|||||||||||||
|
maxLenR |
curr |
max |
len |
curr |
max |
len |
curr |
max |
len |
curr |
max |
len |
|||||||
|
maxLenR |
curr |
max |
len |
curr |
max |
len |
|||||||||||||
59
Here is an iterative Java function that also returns the length of the longest string stored within a binary tree. Notice that this iterative function maintains its own stack as it traverses the tree which makes the iterative solution more complex than the recursive one.
Example 13
/* The Java API documentation suggests that programmers should
* use ArrayDeque for a stack, but we can't use ArrayDeque here
* because it throws a NullPointerException when we push NULL
* on the stack, so we have to write our own stack class. */
private static class Stack<E> extends ArrayList<E> {
void push(E e) { add(e); }
E pop() { return remove(size() - 1); }
}
/** Iteratively finds the length of the
* longest String stored in this binary tree. */
public int maxLen() {
int max = 0;
Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (stack.size() > 0) {
Node curr = stack.pop();
if (curr != null) {
int len = curr.data.length();
if (len > max) {
max = len;
}
stack.push(curr.right);
stack.push(curr.left);
}
}
return max;
}
|
Desk Check |
||||||
|
stack |
curr |
len |
max |
|||
|
[0] |
[1] |
[2] |
||||
60
The recursive maxLenR function performs a pre-order traversal of a binary tree. Here is a recursive function that performs an in-order traversal of a binary search tree and produces an array list containing all the data in the binary search tree in sorted order.
Example 14
/** Returns an array list that
* contains all the data in this tree. */
public ArrayList<String> toListR() {
ArrayList<String> list = new ArrayList<String>();
toListR(list, root);
return list;
}
/** Recursively builds an array list of
* all the data in this binary tree. */
private static void toListR(ArrayList<String> list, Node curr) {
if (curr != null) {
toListR(list, curr.left);
list.add(curr.data);
toListR(list, curr.right);
}
}
|
Desk Check |
|||||||||
|
Function |
Variables |
||||||||
|
toList |
list |
||||||||
|
toListR |
curr |
||||||||
|
toListR |
curr |
curr |
|||||||
|
toListR |
curr |
curr |
curr |
curr |
|||||
|
toListR |
curr |
curr |
|||||||
A pre-order traversal is easier to convert to iteration than an in-order traversal because the pre-order requires each node to be pushed and popped from the stack only once and the in-order requires each node to be pushed and popped twice. Additionally, an in-order traversal requires a return pointer or task flag to be pushed on the stack. During an in-order traversal this task flag determines if the action to be performed on the current node is to check its left node or to process its data. Here is an iterative function converted from the previous recursive function that performs an in-order traversal of a binary search tree. Notice how each node is pushed on the stack twice, once with a flag of CheckLeft and once with a flag of Process.
Example 15
private static enum ToDo { CheckLeft, Process };
private static final class Frame {
Node node;
ToDo todo;
Frame(Node n, ToDo t) { node = n; todo = t; }
}
61
private static final class Stack<E> extends ArrayList<E> {
void push(E e) { add(e); }
E pop() { return remove(size() - 1); }
}
/** Iteratively builds an array list of
* all the data in this binary tree. */
public ArrayList<String> toList() {
ArrayList<String> list = new ArrayList<String>();
if (root != null) {
Stack<Frame> stack = new Stack<Frame>();
stack.push(new Frame(root, ToDo.CheckLeft));
while (stack.size() > 0) {
Frame frame = stack.pop();
Node curr = frame.node;
switch (frame.todo) {
case CheckLeft:
frame.todo = ToDo.Process;
stack.push(frame);
if (curr.left != null) {
stack.push(new Frame(curr.left, ToDo.CheckLeft));
}
break;
case Process:
list.add(curr.data);
if (curr.right != null) {
/* We no longer need the stack frame for the
* current node, so reuse it for the right child. */
frame.node = curr.right;
frame.todo = ToDo.CheckLeft;
stack.push(frame);
}
break;
}
}
}
return list;
}
|
Desk Check |
||||||
|
list |
||||||
|
stack |
frame |
|||||
|
node |
todo |
|||||
62
Fibonacci Series
Consider the Fibonacci series that starts with 0 and 1: 0, 1, 1, 2, 3, 5, 8… which mathematicians define as a recursive function:
fib(n) = fib(n−2) + fib(n−1)
fib(1) = 1
fib(0) = 0
Here is a recursive Java function to compute the nth Fibonacci number. Notice that this recursive function is essentially a direct translation of the mathematical function into Java.
Example 16
/** Recursively computes the nth Fibonacci number. */
public static long fibonacci(int n) {
switch (n) {
case 0: return 0;
case 1: return 1;
default: return fibonacci(n-2) + fibonacci(n-1);
}
}
|
Desk Check |
||||||||||||||
|
Function |
Variables |
|||||||||||||
|
fibonacci |
n |
return |
||||||||||||
|
4 |
||||||||||||||
|
fibonacci |
n |
return |
n |
return |
||||||||||
|
fibonacci |
n |
return |
n |
return |
n |
return |
n |
return |
||||||
|
fibonacci |
n |
return |
n |
return |
||||||||||
Figure 24 shows the order in which the recursive fibonacci function calls itself and returns from those calls.
Figure 24: Function calls and returns for the recursive fibonacci function.
63
Here is an iterative Java function that computes the nth Fibonacci number by maintaining its own stack. This is a very complex way to compute Fibonacci numbers.
Example 17
/** Iteratively computes the nth fibonacci number. */
public static long fibonacci(int n) {
long fib = 0;
if (n > 0) {
int[] stack = new int[n];
int frame = -1;
stack[++frame] = n;
while (frame >= 0) {
n = stack[frame--];
switch (n) {
case 0:
break;
case 1:
fib++;
break;
default:
stack[++frame] = n - 1;
stack[++frame] = n - 2;
break;
}
}
}
return fib;
}
|
Desk Check |
|||||||
|
stack |
frame |
n |
fib |
||||
|
4 |
|||||||
|
[0] |
[1] |
[2] |
[3] |
||||
Of course there is a shorter and faster iterative solution that doesn’t maintain its own stack for computing the nth Fibonacci number. This shorter solution uses the fact that any Fibonacci number is simply the sum of the previous two Fibonacci numbers. So this solution simply adds two numbers repeatedly until it has computed the nth Fibonacci number.
Example 18
/** Iteratively computes the nth Fibonacci number. */
public static long fibonacci(int n) {
long past = 0;
long present = 1;
while (n > 0) {
long future = past + present;
past = present;
present = future;
--n;
}
return past;
}
|
Desk Check |
|||
|
future |
past |
present |
n |
|
4 |
|||
64
We can also convert the iterative fibonacci function in the previous example into a tail recursive function. This tail recursive function is much more efficient than the original recursive fibonacci function in example 16 because it adds the previous two Fibonacci numbers to produce the next number instead of repeatedly adding 0 and 1 as example 16 does.
Example 19
public static long fibonacci(int n) {
return fibonacciR(0, 1, n);
}
/** Recursively computes the nth Fibonacci number. */
private static long fibonacciR(long past, long present, int n) {
if (n == 0) {
return past;
}
return fibonacciR(present, past + present, n - 1);
}
|
Desk Check |
||||
|
Function |
Variables |
|||
|
fibonacci |
n |
return |
||
|
4 |
||||
|
fibonacciR |
past |
present |
n |
return |
|
fibonacciR |
past |
present |
n |
return |
|
fibonacciR |
past |
present |
n |
return |
|
fibonacciR |
past |
present |
n |
return |
|
fibonacciR |
past |
present |
n |
return |
Interestingly there is even a formula for computing the nth Fibonacci number.
fib(n) =
φn − (−φ)−n
√
5
where φ is the golden ratio
φ =
1 + √5
2
≈ 1.618
Example 20
private static final double SQRT5 = Math.sqrt(5);
private static final double GOLDEN = (1 + SQRT5) / 2;
/** Computes the nth Fibonacci number using a formula. */
public static long fibonacci(int n) {
double numer = Math.pow(GOLDEN, n) - Math.pow(-GOLDEN, -n);
return Math.round(numer / SQRT5);
}
|
Desk Check |
||||
|
SQRT5 |
GOLDEN |
n |
numer |
return |
|
2.236 |
1.618 |
4 |
||
65
Files and Directories
One common use of recursion is to process all the files in a file system directory and its sub directories. Below is a recursive function that builds a list of all files and sub directories in a directory. The list is sorted so that the files appear first in alphabetical order and the sub directories and their files appear second also in alphabetical order like this:
volunteer
volunteer\flora.jpg
volunteer\soccer
volunteer\soccer\improvements.rtf
volunteer\soccer\U6
volunteer\soccer\U6\rules.docx
volunteer\soccer\U6\Schedule.xlsx
Example 21
/** Returns a list of all files and sub directories
* in a directory and its sub directories. */
public static ArrayList<File> listFiles(File[] dir) {
ArrayList<File> list = new ArrayList<File>();
listFilesR(list, dir);
return list;
}
/** Recursively lists the files in a directory. */
private static void listFilesR(ArrayList<File> list, File[] dir) {
/* Sort the directory so that files are listed
* in alphabetical order first, then directories
* are listed in alphabetical order second. */
Arrays.sort(dir, fileComp);
int i = 0;
// Add all non directory files to the list.
for (; i < dir.length; ++i) {
File file = dir[i];
if (file.isDirectory()) {
break;
}
list.add(file);
}
// Process all directories.
for (; i < dir.length; ++i) {
// Add this directory to the list of files.
File file = dir[i];
list.add(file);
File[] subdir = file.listFiles();
if (subdir != null) {
// Recurse to process the files in this directory.
listFilesR(list, subdir);
}
}
}
66
/** A Comparator to sort files and sub directories.
* Files are listed first in alphabetical order, and
* sub directories are listed second in alphabetical order. */
private static final FileComparator fileComp = new FileComparator();
private static class FileComparator implements Comparator<File> {
@Override
public int compare(File f1, File f2) {
boolean f1IsDir = f1.isDirectory();
boolean f2IsDir = f2.isDirectory();
int ret;
if (f1IsDir == f2IsDir) {
String n1 = f1.getName().toLowerCase();
String n2 = f2.getName().toLowerCase();
ret = n1.compareTo(n2);
}
else {
ret = f1IsDir ? 1 : -1;
}
return ret;
}
}
Of course this recursive function can be converted to an iterative one by creating and maintaining a stack. In the following example, the stack holds only directories, and the files and directories are added to a list just as in the previous example.
Example 22
/** Returns a list of all files and sub directories
* in a directory and its sub directories. */
public static ArrayList<File> listFiles(File[] dir) {
// A list of files and directories.
ArrayList<File> list = new ArrayList<File>();
// A stack of directories.
Stack<File> stack = new Stack<File>();
RevDirComparator revComp = new RevDirComparator();
Arrays.sort(dir, revComp);
addAndPush(list, stack, dir);
while (!stack.isEmpty()) {
// Add this directory to the list of files.
File subdir = stack.pop();
list.add(subdir);
// Process the files in this directory.
dir = subdir.listFiles();
if (dir != null) {
Arrays.sort(dir, revComp);
addAndPush(list, stack, dir);
}
}
return list;
}
67
/** Adds all non directory files to list
* and pushes all directories on stack. */
private static void addAndPush(ArrayList<File> list,
Stack<File> stack, File[] dir) {
int i = 0;
// Add all non directory files to the list.
for (; i < dir.length; ++i) {
File file = dir[i];
if (file.isDirectory()) {
break;
}
list.add(file);
}
// Push all directories on the stack.
for (; i < dir.length; ++i) {
File file = dir[i];
stack.push(file);
}
}
/** A Comparator to sort files and sub directories. Files are listed
* first in alphabetical order. Sub directories are listed second in
* reverse alphabetical order because sub directories will be pushed
* on and then popped off a stack. */
private static final class RevDirComparator implements Comparator<File> {
@Override
public int compare(File f1, File f2) {
boolean f1IsDir = f1.isDirectory();
boolean f2IsDir = f2.isDirectory();
int ret;
if (f1IsDir == f2IsDir) {
String n1 = f1.getName().toLowerCase();
String n2 = f2.getName().toLowerCase();
ret = n1.compareTo(n2);
if (f1IsDir) {
ret = -ret; // Reverse the order of sub directories.
}
}
else {
ret = f1IsDir ? 1 : -1;
}
return ret;
}
}
68
Converting Iteration to Recursion
To convert an iterative function to a recursive one, a programmer must divide a problem into smaller self-similar problems. Consider an iterative binary search function.
Example 23
/** If key is in list, returns any index where key is
* located within list; otherwise returns -insertPoint - 1.
* Assumes list is already sorted. */
public static int binarySearch(float[] list, float key) {
int left = 0;
int right = list.length - 1;
while (left <= right) {
int mid = left + ((right - left) >>> 1);
float cmp = key - list[mid];
if (cmp > 0) {
left = mid + 1;
} else if (cmp < 0) {
right = mid - 1;
} else {
return mid;
}
}
// key is not present in list, but if it
// were, it would be stored at location left.
return -(left + 1);
}
|
Desk Check |
|||||||||||||
|
list |
|||||||||||||
|
−2.1 |
−1 |
3.9 |
6.2 |
7.1 |
9.7 |
10 |
12 |
13.1 |
15.6 |
18 |
19 |
20.1 |
24.5 |
|
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
[8] |
[9] |
[10] |
[11] |
[12] |
[13] |
|
key |
left |
right |
mid |
cmp |
return |
|
15.6 |
|||||
An iterative binary search function can be converted into a recursive function by realizing that a binary search repeatedly divides a list into halves and restricts the search to one of those halves. This leads to a simple recursive implementation. Notice within the binarySearchR function that each time it calls itself, it is dividing the search interval in half.
69
Example 24
/** If key is in list, returns any index where key is
* located within list; otherwise returns -insertPoint - 1.
* Assumes list is already sorted. */
public static int binarySearch(float[] list, float key) {
return binarySearchR(list, key, 0, list.length - 1);
}
/** Recursively searches an array for any occurence of key. */
private static int binarySearchR(
float[] list, float key, int left, int right) {
if (left <= right) {
int mid = left + ((right - left) >>> 1);
float cmp = key - list[mid];
if (cmp > 0) {
return binarySearchR(list, mid + 1, right, key);
} else if (cmp < 0) {
return binarySearchR(list, left, mid - 1, key);
} else {
return mid;
}
}
// key is not present in list, but if it
// were, it would be stored at location left.
return -(left + 1);
}
|
Desk Check |
|||||||||||||
|
list |
|||||||||||||
|
−2.1 |
−1 |
3.9 |
6.2 |
7.1 |
9.7 |
10 |
12 |
13.1 |
15.6 |
18 |
19 |
20.1 |
24.5 |
|
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
[8] |
[9] |
[10] |
[11] |
[12] |
[13] |
|
Function |
Variables |
|||||
|
binarySearch |
key |
return |
||||
|
15.6 |
||||||
|
binarySearchR |
key |
left |
right |
mid |
cmp |
return |
|
15.6 |
||||||
|
binarySearchR |
key |
left |
right |
mid |
cmp |
return |
|
15.6 |
||||||
|
binarySearchR |
key |
left |
right |
mid |
cmp |
return |
|
15.6 |
||||||
|
binarySearchR |
key |
left |
right |
mid |
cmp |
return |
|
15.6 |
||||||
70
Future Value
The future value of an investment with a constant growth rate can be calculated using this formula: f = a (1 + r)n where f is the future value, a is the investment amount (also known as the principal), r is the growth rate per period, and n is the total number of periods throughout the life of the investment. Here is a function that uses this formula to compute the future value.
Example 25
/** Computes the future value of an investment with
* compound growth and a fixed annual growth rate. */
public static long futureValue(long principal,
double annualRate, int years, int periodsPerYear) {
double rate = annualRate / periodsPerYear;
int periods = years * periodsPerYear;
double fv = principal * Math.pow(1 + rate, periods);
return (long)Math.rint(fv);
}
|
Desk Check |
||||||
|
principal |
annualRate |
years |
periodsPerYear |
rate |
periods |
fv |
|
10000 |
0.06 |
2 |
4 |
|||
The formula for computing the future value is derived using calculus and accounts for compound growth or interest. The future value can also be computed using iteration where the simple interest for one investment period is computed and added to the investment principal during each iteration.
Example 26
/** Iteratively computes the future value of an investment
* with compound growth and a fixed annual growth rate. */
public static long futureValue(long principal,
double annualRate, int years, int periodsPerYear) {
double rate = annualRate / periodsPerYear;
int periods = years * periodsPerYear;
for (int i = 1; i <= periods; i++) {
principal += (long)Math.rint(principal * rate);
}
return principal;
}
|
Desk Check |
||||||
|
i |
principal |
annualRate |
years |
periodsPerYear |
rate |
periods |
|
10000 |
0.06 |
2 |
4 |
|||
71
Of course this iterative function can be converted to a tail recursive function that during each function call computes the simple interest for one investment period and adds that interest to the principal.
Example 27
public static long futureValue(long principal,
double annualRate, int years, int periodsPerYear) {
double rate = annualRate / periodsPerYear;
int periods = years * periodsPerYear;
return futureValueR(principal, rate, periods);
}
/** Recursively computes the future value of an investment
* with compound growth and a fixed annual growth rate. */
private static long futureValueR(long principal, double rate, int period) {
if (--period < 0) {
return principal;
}
principal += (long)Math.rint(principal * rate);
return futureValueR(principal, rate, period);
}
|
Desk Check |
|||||||
|
Function |
Variables |
||||||
|
futureValue |
principal |
annualRate |
years |
periodsPerYear |
rate |
periods |
return |
|
10000 |
0.06 |
2 |
4 |
||||
|
futureValueR |
principal |
rate |
period |
return |
|||
|
futureValueR |
principal |
rate |
period |
return |
|||
|
futureValueR |
principal |
rate |
period |
return |
|||
|
futureValueR |
principal |
rate |
period |
return |
|||
|
futureValueR |
principal |
rate |
period |
return |
|||
|
futureValueR |
principal |
rate |
period |
return |
|||
|
futureValueR |
principal |
rate |
period |
return |
|||
|
futureValueR |
principal |
rate |
period |
return |
|||
|
futureValueR |
principal |
rate |
period |
return |
|||
72
Conclusions
Iteration and recursion are equally powerful tools for causing a computer to repeat a group of statements. All recursive functions can be rewritten as iterative functions which a programmer may need to do if she is writing a program in a language that lacks recursion or that does not optimize recursion. All iterative functions can be rewritten as recursive functions which a programmer may need to do if he is writing a program in a language that lacks iteration.