CISC 3115
Modern Programming Techniques
Lecture #5
Recursion


Motivation

Given a file containing an arbitrary number of integers, write a program that reads in the integers and prints them in reverse … without using an array. 

import java.util.*;
import java.io.*;

public class PrintInReverse{
	public static void main(String [] args) throws Exception {
		String filename = "../../numbers.text";

		int count = getNumIntsInFile(filename);
		for (int i = count; i >t; 0; i--)
			printNthInt(filename, i);
	}

	static int getNumIntsInFile(String filename) throws Exception {
		Scanner scanner = new Scanner(new File(filename));
		int count = 0;

		while (scanner.hasNextInt()) {
			count++;
			scanner.nextInt();	// skip
		}

		return count;
	}

	static void printNthInt(String filename, int n) throws Exception  {
		Scanner scanner = new Scanner(new File(filename));
		// skip n-1 integers
		for (int i = 1; i < n; i++)
			scanner.nextInt();
		System.out.println(scanner.nextInt()); // Print the n'th integer
	}
}

Recursion

Recursive Method

Recursive Methods Can Be Written in Java

static void readANdPrintNumbers(Scanner scanner) {
	if (!scanner.hasNextInt())
		return;
	else {
		int num = scanner.nextInt();
		System.out.println(num);
		readAndPrintdNumbers(scanner);
	}
}
What about this one?: 
static void readANdPrintNumbers(Scanner scanner) {
	if (!scanner.hasNextInt())
		return;
	else {
		int num = scanner.nextInt();
		readAndPrintdNumbers(scanner);
		System.out.println(num);
	}
}

Anatomy of a Recursive Function

To Write Recursively You Have to Think Recursively!

Recursive Data

Arrays

An array is a sequence of elements; a sequence of elements is either:

Strings

An string is a sequence of characters; a sequence of characters is either:

Non-negative Integers

A non-negative integer is either:

Recursive Algorithms

Arrays

The Need for Subarrays

Often — and especially in the context of recursion involving arrays — the algorithm calls for working with subarrays. This is because we often process/visit one element at a time (typically the first or last) and after that, we process the rest of the array (this is especially true with recursion). HOWEVER, while the rest of the array is also a sequence of elements, it is NOT an array in the sense of a Java array. As an example, suppose we had a method f(int [] arr) that accepted an array. The following is clearly legal: 
int [] arr = new int [] {10, 20, 30, 40};
f(arr);
i.e., we can clearly pass an array to a method expecting an array (of the same element type of course). But we CAN'T pass to f the sequence consisting of all the elements but the first (i.e., the rest of the array.

One solution is to copy those elements to a new array (whose size is one less than that of the original array; after which we can then pass this new array to f: 

int [] temp = new int [arr.length-1];
for (int i = 0; i < temp.length; i++)
	temp[i] = arr[i+1];		// copying all the elements except arr[0] to temp
f(temp);
The problem with this approach is the overhead of creating a new array and copying the elements from the original array. And this is exacerbated in a recursive context by the fact that this is done over and over again at each level of the recursion.

Subarrays to the Rescue

Here is a section of my 1115 notes on subarrays.

To solve the above issue, we use the (original) array, together with the two indexes denoting the boundaries of the rest of the array, i.e., a subarray, as described in the overview. These indexes are often named low/high, first/last, etc.

We can then have our method accept a subarray (rather than an array) by having three parameters corresponding to the array and the two bounds.

The Use of a Wrapper Method

While there are algorithms that explicitly present the caller with a subarray for an argument (for example a printSubarray method), the use of the subarray is often introduced in order to avoid the performance overhead described below. In such a case, the perspective of the original caller is the invocation of a method on the entire array (and the subarray gets introduced as part of the recursive call on the rest of the array). As such, we wish to present the caller with a natural (i.e., intuitive) method signature, one involving simply the array and no bounds. This is accomplished by introducing a wrapper method that presents to the caller THEIR desired interface, and then provides the proper arguments to the subarray method: 
f(int [] array) {f(array, 0, array.length-1);}

f(int [] array, int lo, int hi) {…}

Printing an array

Notes:

Printing an array in reverse

or

Searching an array for a value (contains)

Finding a value in an array (find)

Need to return the position

Summing an array

Max of an array

Checking for 'Palindrome' Array

Binary search

Strings

Printing a string

Checking for palindromes

Numerics (Integers)

Factorial

Fibonacci numbers

Addition using increment

Test for Evenness

Equality

Towers of Hanoi

  • 3 towers, we'll call them A, B, C
  • Move from A (source) to C (dest) using B (as a temporary)
  • n rings-- smallest is 1, largest is n
  • only move one ring at a time
  • larger rings may not be moved onto smaller rings
  • To solve:

    Recursion Within the Context of a Class

    Suppose we have a Container class: 
    class Container {
	…
	public int find(int value) {…}
	public boolean contains(int value) {return find(value) != -1;}
	…
	private int size = 0;
	private int [] arr = new int[CAPACITY];
}

    Code Used in This Lecture