Recursion

From Knowledge Kitchen
Jump to navigation Jump to search


Recursion basics

Recursion = methods calling themselves


Common uses

Recursion can be helpful any time a big problem can be broken down into multiple sub-problems that are the same basic process as the big problem.

Common uses include:

For those who are math-inclined, this write-up from Princeton has a nice overview.

Basic examples

Notice that in all examples, there is a finite number of recursive iterations. Infinite recursions would cause a StackOverFlow error in our code.

Basic recursion mechanics

This example simply shows the mechanics of recursion, while not doing anything especially useful. In this case, we stop the recursion after a fixed number of iterations. In real uses, recursion often ends itself without such a hack.

package edu.nyu.cs.fb1258;

public class BasicRecursion {
  public static int numIterations = 5;
  
  public static void main(String[] args) {
    System.out.println("Starting the main method...");
    doIt();
    System.out.println("Back in main...");
  }
  
  public static void doIt() {
    System.out.println("Doing it...");
    if (numIterations > 0) {
      numIterations--;
      doIt();
    }
  }

}


Drinking coffee

package edu.nyu.cs.fb1258;

public class CoffeeCup {

  private int numSips = 15;
  
  public CoffeeCup() {
    
  }
  
  public CoffeeCup(int n) {
    System.out.println("Constructing CoffeeCup object...");
    this.numSips = n;
  }

  public boolean isEmpty() {
    if (this.numSips == 0) {
      return true;
    }
    else return false;
  }
  
  public void takeSip() {
    if (!this.isEmpty()) {
      this.numSips--;
      System.out.println("Slurp...");
    }
  }
  
  public void guzzleCup() {
    System.out.println("guzzleCup starting...");
    if (!this.isEmpty()) {
      this.takeSip();
      guzzleCup();
    }
    System.out.println("guzzleCup ending...");
  }
  
  public static void main(String[] args) {
    System.out.println("Main starting...");
    CoffeeCup myCup = new CoffeeCup();
    myCup.guzzleCup();
    System.out.println("Main ending...");
  }

}


Koch Snowflake

This is my simplification of a classic variety of fractal called a Koch Snowflake. I've avoided any math, so it only grows in one direction.

package edu.nyu.cs.fb1258;

import processing.core.*;

/**
 * Example of recursion.  This class  represents a simplified Koch Snowflake
 * @author Foo Barstein
 * @version 2
 */
public class KochSnowflake extends PApplet {

	public static void main(String[] args) {
		PApplet.main("edu.nyu.cs.fb1258.KochSnowflake");
	}
	
	/**
	 * width and height of the window
	 **/
	int width = 600;
	int height = 600;
	
	/**
	 * how many levels deep of recursion  dive... note that this is not the  same concept as how many times a loop  iterates
	 */
	int levelsOfRecursion = 10;
	
	/**
	 * a counter to keep track of how many  times our recursive method is called
	 */
	int methodCallCounter = 0;
	
	/**
	 * override PApplet's settings method
	 */
	public void settings() {
		this.size(width, height);
	}
	
	/**
	 * override PApplet's setup() method
	 */
	public void setup() {
		//set up the window
		this.stroke(255, 0, 0); //red
		
		//create the points that represent  the beginning and ending of the  first line
		Point p1 = new Point(0, height); // bottom left point
		Point p2 = new Point(width,  height); //bottom right point
		
		//call the makeLine method for the  first time
		this.makeLine(p1, p2,  levelsOfRecursion);
	}

	/**
	 * This method takes two points and  draws a line between them.  It also  calculates the midpoint of this line,  offsets its y coordinate a bit, and  draws a line from the first point to  this midpoint, and another from this  midpoint to the second point.
	 * @param p1 starting point of a line
	 * @param p2 ending point of a line
	 * @param recursionLevel keeps track  of which level of recursion we are  currently at... in descending order
	 */
	public void makeLine(Point p1, Point  p2, int recursionLevel) {

		//increment the counter that keeps  track of how many times we called  this method
		methodCallCounter++; 
		
		//debugging
		System.out.println("Currently at  recursion level " +  recursionLevel);
		System.out.println("We have called  this method " + methodCallCounter  + " times.");

		//subtract from the counter that  keeps track of how many recursive  levels we've processed
		recursionLevel--; 
		
		//stop recursing after we've  reached the last level
		if (recursionLevel > 0) {
			
			//draw a line between the two  points
			this.stroke(0, 255, 0);
			this.line(p1.x, p1.y, p2.x, p2.y);

			//calculate the midpoint of  the line
			float midX = ((p2.x + p1.x) /  2); //the mid x coordinate
			float midY = ((p2.y + p1.y) /  2); //the mid y coordinate
			midY = midY - midY/2; // subtract some factor from the  y position so that each  successive line is higher up  the screen.
			Point midPoint = new Point(( int) midX, (int) midY); //new  point object representing this  midpoint
//			System.out.println(midPoint.x  + ":" + midPoint.y); //debugging
			
			//draw a line between the  first point and the midpoint
			this.stroke(255, 0, 0);
			this.line(p1.x, p1.y, midPoint.x,  midPoint.y);
			
			//draw a line between the  midpoint and the second point
			this.line(midPoint.x, midPoint.y, p2 .x, p2.y);	
			
			//recursively call this method  again to do the same thing  with each of the new lines we  just made
			this.makeLine(p1, midPoint,  recursionLevel); //repeat this  procedure with the line from  p1 to the midpoint
			this.makeLine(midPoint, p2,  recursionLevel); //repeat this  procedure with the line from  the midpoint to p2
		}
		
	}

	public void draw() {
	}
	
}
	
/**
 * Class that represents an x,y coordinate  on the screen
 * @author Foo Barstein
 *
 */
class Point {
	int x = 0;
	int y = 0;
	
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

Fibonacci numbers

See textbook for explanation of Fibonacci numbers.

/**
 * Program to compute the Fibonacci number at any given index.
 * Fibonacci numbers are a sequence such as 0, 1, 1, 2, 3, 5, 8, 13, 21, 33, 54, etc...
 * They start with 0, 1, and every successive number is the sum of the two previous numbers.
 */

package edu.nyu.cs.fb1258;

import java.util.Scanner;

public class ComputeFibonacci {

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		System.out.println("Please enter an index for a Fibonacci number: ");
		int index = input.nextInt();

		//get the Fibonacci number at this index
		long fib = getFibonacciAtIndex(index);
		
		System.out.println("The Fibonacci number at index " + index + " is " + fib);
	}
	
	public static int getFibonacciAtIndex(int index) {
		if (index == 0) {
			//The Fibonacci number at index zero is zero
			return 0; 
		}
		else if (index == 1) {
			//The Fibonacci number at index one is one
			return 1; 
		}
		else {
			//for all other indexes, the Fibonacci number is the sum of the two previous Fibonacci numbers.
			return getFibonacciAtIndex(index - 1) + getFibonacciAtIndex(index - 2);
		}
	}

}

Computing powers

Computing a positive integer power of a number is easily seen as a recursive process. Consider a^n (a to the power of n):

  • If n = 0, a^n is 1 (by definition)
  • If n > 0, a^n is a * a^(n-1)
package edu.nyu.cs.fb1258;

import java.util.Scanner;

/**
 * An example of solving power equations using recursion.  Only works with integers below 2^32.
 * @author Foo Barstein
 * @version 1
 */
public class Power {

  public static void main(String[] args) {
    int base, exp;
    int answer;
    
    Scanner scn = new Scanner(System.in);
    System.out.println("Welcome to the power program!");
    System.out.println("Please use integers only.");
    
    //get base
    System.out.print("Enter the base you would like to raise to: ");
    base = scn.nextInt(); //assume valid int
    
    //get exponent
    System.out.print("Enter the power you would like to raise to: ");
    exp = scn.nextInt();
    
    //get answer
    answer = Power.power(base, exp);
    System.out.println(base + " raised to the " + exp + " is " + answer);

  }
  
  /**
   * Calculates powers using recursion.
   * @param base The base number
   * @param exp The exponent to raise the base to
   * @return The result of the power calculation.
   */
  public static int power(int base, int exp) {
    int pow; //the value that will be returned

    //if the exponent is 0, set pow to 1
    if (exp == 0) {
      //any number raised to the 0th power is = 1
      pow = 1;
    }
    //otherwise set pow to base * base^(exp-1)... recursion!
    else {
      //use recursion to calculate the result
      pow = base * power(base, exp-1);
    }

    //System.out.println(pow); //debugging
    
    //return pow
    return pow;
  }
  
}

Counting and summing digits

The problem of counting the digits in a positive integer or summing those digits can be solved recursively. For example, to count the number of digits think as follows:

  • If the integer is less than 10, there is only one digit (the base case).
  • Otherwise, the number of digits is 1 (for the units digit) plus the number of digits in the rest of the integer (what's left after the units digit is taken off). For example, the number of digits in 3278 is 1 + the number of digits in 327.

The following is the recursive algorithm implemented in Java.

package edu.nyu.cs.fb1258;

import java.util.Scanner;

public class DigitCounter {

	public static int numDigits(int num) {
		int result; //will hold the number of digits in the num
		
		//numbers less than ten contain only 1 digit
		if (num < 10) {
			result = 1;
		}
		//if num is more than 10, we know it contains one digit plus however many digits are left after removing the first
		else {
			result = 1 + DigitCounter.numDigits(num / 10);
		}
		
		//return result
		return result;
	}
	
	public static void main(String[] args) {
		int num, digits;
		
		Scanner scn = new Scanner(System.in);
		System.out.println("Welcome to the digit counter program!");
		System.out.println("Please use integers only.");
		
		//get base
		System.out.print("Enter the number you would like to count the digits of: ");
		num = scn.nextInt(); //assume valid int
		
		//calculate digits
		digits = DigitCounter.numDigits(num);
		System.out.println("The number " + num + " has " + digits + " digits");

		

	}

}

Additional challenge

Try adding a static method named sumDigits that finds the sum of the digit in a positive integer. Also add code to main to test your method. The algorithm for sumDigits is very similar to numDigits; you only have to change two lines!

Flipping strings backwards

Reversing a string can also be done recursively. The algorithm for reversing amounts to the following:

  • if the string to reverse is only 1 character long, return that single character
  • otherwise, return that last character appended to the remaining part of the string in reverse
package edu.nyu.cs.fb1258;

import java.util.Scanner;

/**
 * Flips a string backwards using recursion.
 * @author Foo Barstein
 * @version 1
 *
 */
public class Backwards {

	public static void main(String[] args) {
		String original, backwards;
		
		//ask the user for a string
		Scanner scn = new Scanner(System.in);
		System.out.println("Welcome to the string backwards converter!");
		
		//get user input
		System.out.print("Enter the string you would like to flip backwards: ");
		original = scn.nextLine();
		
		//generate backwards version
		backwards = Backwards.backwards(original);
		System.out.println("The string '" + original + "' backwards is '" + backwards + "'.");

	}
	
	public static String backwards(String original) {
		String backwards = ""; //start off with a blank slate
		
		//System.out.println(original); //debugging
		
		//a zero or one-character string backwards is the same as forwards
		if (original.length() <= 1) {
			return original;
		}
		else {
			//add the last character from the original to the backwards version
			char lastChar = original.charAt(original.length() - 1);
			backwards += lastChar; //the last character

			//flip the remaining part of the original and add it to this backwards version
			String remainder = original.substring(0, original.length() -1); //everything up to the last character
			backwards += Backwards.backwards(remainder); //recursion!
		}
		
		return backwards;
	}

}

Linear search

Linear search can be done either recursively or iteratively. This example shows both. The code consists of two files.

IntegerListS.java

package edu.nyu.cs.fb1258;

/**
 * A class representing a list of integers.  Performs a linear search using recursion.  
 * @author Foo Barstein
 * @version 2
 *
 */
public class IntegerListS {
	private int[] list; //values in the list
	
	/**
	 * Constructs a list of the given size.
	 * @param size The length of the list to create
	 */
	public IntegerListS(int size) {
		this.list = new int[size];
	}
	
	/**
	 * Fills the list with integers between 1 - 100, inclusive.
	 */
	public void randomize() {
		for (int i=0; i<list.length; i++) {
			this.list[i] = (int) (Math.random() * 100) + 1;
		}
	}
	
	public void print() {
		for (int i=0; i<list.length; i++) {
			System.out.println(i + ":\t" + this.list[i]);
		}
	}
	
	/**
	 * Returns the index of the first occurrence of the target within the list **without using recursion**.  Returns -1 if target does not appear in the list.
	 * @param target The value to search for
	 * @return The index of the first occurrence of the target within the list.
	 */
	public int linearSearch(int target) {
		//linear search the 'old fashioned way' without recursion
		int location = -1;
		//iterate through all values and compare to target value
		for (int i=0; i<list.length && location == -1; i++) {
			if (list[i] == target) {
				location = i;
			}
		}
		//return index, if any, where the value resides
		return location;
	}
	
	/**
	 * A more user-friendly and abstract method that simply calls linearSearchR with the second parameter hard-coded.
	 * @param target The value to search for
	 * @return The index of the first occurrence of the target within the list.
	 */
	public int linearSearchRec(int target) {
		//call the linearSearchR method with the starting index hard-coded as 0
		return linearSearchR(target, 0);
	}
	
	/**
	 * Recursive implementation of the linear search.  Begins the search at index lo.  The algorithm works recursively as follows if you are looking for an item starting from index i:
	 * - if i exceeds the last index of the list, the item is not found (return -1)
	 * - if the item is at list[i], return i
	 * - if the item is not at list[i], do a linear search starting from index i+1
	 * @param target The value to search for
	 * @param lo The index of the position at which to start the search
	 * @return The index of the first occurrence of the target within the list
	 */
	public int linearSearchR(int target, int lo) {
		//do a recursive linear search of list from the starting index, lo
		
		int location;

		// if the index exceeds the last index of the list, the item is not found (return -1)
		if (lo > this.list.length - 1) {
			location = -1;
		}
		
		// if the item is at list[lo], return i
		else if (target == list[lo]) {
			location = lo;
		}

		// if the item is not at list[i], do a linear search starting from index i+1
		else {
			location = linearSearchR(target, lo + 1);
		}
		
		return location;
	}
	
	/**
	 * Sort the list in ascending order using the selection sort algorithm.
	 */
	public void selectionSort() {
		int minIndex;
		for (int i=0; i<list.length; i++) {
			//find the smallest element in the list starting at location i
			minIndex = i;
			for (int j = i+1; j<list.length; j++) {
				if (list[j] < list[minIndex]) {
					minIndex = j;
				}
			}
			
			//swap list[i] with smallest element
			int temp = list[i];
			list[i] = list[minIndex];
			list[minIndex] = temp;			
			
		}
	}

	public static void main(String[] args) {
	}
}

IntegerListTest.java

package edu.nyu.cs.fb1258;

import java.util.Scanner;

/**
 * Test of the IntegerListS class.
 * @author Foo Barstein
 * @version 2
 *
 */
public class IntegerListTest {

	private static IntegerListS list = new IntegerListS(10);
	private static Scanner scn = new Scanner(System.in);
	
	/**
	 * Create a list, display the menu, and then repeatedly do what the user asks until they quit.
	 * @param args Command-line arguments, if any.  These are ignored.
	 */
	public static void main(String[] args) {
		printMenu();
		int choice = scn.nextInt();
		while (choice != 0) {
			dispatch(choice);
			printMenu();
			choice = scn.nextInt();			
		}
	}
	
	/**
	 * Does what the menu item calls for.
	 * @param choice
	 */
	public static void dispatch(int choice) {
		int loc;
		switch (choice) {
		case 0:
			System.out.println("Bye!");
			break;
		case 1:
			System.out.println("How big should the list be?");
			int size = scn.nextInt();
			list = new IntegerListS(size);
			list.randomize();
			break;
		case 2:
			list.selectionSort();
			break;
		case 3:
			System.out.print("Enter the value to look for: ");
			loc = list.linearSearch(scn.nextInt());
			if (loc != -1) {
				System.out.println("Found at location " + loc);
			}
			else {
				System.out.println("Not in list");
			}
			break;
		case 4:
			System.out.print("Enter the value to look for: ");
			loc = list.linearSearchRec(scn.nextInt());
			if (loc != -1) {
				System.out.println("Found at location " + loc);
			}
			else {
				System.out.println("Not in list");
			}
			break;
		case 5:
			list.print();
			break;
		default:
			System.out.println("Sorry, invalid choice");
			
		}
	}
	
	public static void printMenu() {
		System.out.println("\nMenu    ");
		System.out.println("====    ");
		System.out.println("0: Quit");
		System.out.println("1: Create new list elements (** do this first !! **)");
		System.out.println("2: Sort the list using selection sort");
		System.out.println("3: Find an element in the list using linear search without recursion");
		System.out.println("4: Find an element in the list using linear search with recursion");
		System.out.println("5: Print the list");
		System.out.println("\nEnter your choice: ");
	}

}

Payroll

An example of using recursion in a business use-case, where we need to compute how many employees worked overtime, given a data file with all employees' hours.

This example consists of several discrete files.

Employee.java

package edu.nyu.cs.fb1258;

/**
 * Represents an hourly wage laborer.
 * @author Foo Barstein
 * @version 2
 */
public class Employee {
	String name;
	int hours;	//hours worked
	double rate; //hourly pay rate
	
	/**
	 * Sets up the Employee object with the given data.
	 * @param name Name of employee
	 * @param hours hours worked
	 * @param rate hourly pay rate
	 */
	public Employee(String name, int hours, double rate) {
		this.name = name;
		this.hours = hours;
		this.rate = rate;
	}
	
}

Payroll.java

package edu.nyu.cs.fb1258;

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

/**
 * Represents a list of employees.
 * @author Foo Barstein
 * @version 2
 * 
 */
public class Payroll {

	final int MAX = 30;
	Employee[] payroll = new Employee[MAX];
	int numEmployees = 0;
	boolean hasData = false;
	
	/**
	 * Reads the list of employee wage data from the given file.
	 * @param file The name of the file to read from.
	 */
	public void readPayrollInfo(String file) {
		String line;		//a line in the file
		String name;		//name of an employee
		int hours;		//hours worked
		double rate;		//hourly pay rate
		
		Scanner fileScan, lineScan;
		
		try {
			//open the file
			fileScan = new Scanner(new File(file));
			
			//loop as many times as there are lines in the file
			while (fileScan.hasNext()) {
				//get the next available line
				line = fileScan.nextLine();
	
				lineScan = new Scanner(line); //did you know you could make a Scanner out of each line?!
				
				//get the name out of the line
				name = lineScan.next();
				
				//try to get the hour sand rate data out of the line... this may fail if the data is not suitable for the data types of these variables, or if the array of Employees is full already
				try {
					//get the hours and rate out of the line
					hours = lineScan.nextInt();
					rate = lineScan.nextDouble();

					//System.out.println(name + "," + hours + "," + rate); //debugging

					//create a new Employee with this data and add to the array
					payroll[numEmployees] = new Employee(name, hours, rate);
					
					//increment the employee counter
					numEmployees++;
				}
				catch(InputMismatchException e) {
					//one of the values in the line was of the wrong data type
					System.out.println("Error in input.  Line ignored.");
					System.out.println(line);
				}
				catch (ArrayIndexOutOfBoundsException e) {
					//the employees array is full
					System.out.println("Too many employees!");
				}
				
			} //try
			
			//close the file
			fileScan.close();
			
			//keep track that we have read the data
			hasData = true;
			
		}
		catch(FileNotFoundException e) {
			//the data file could not be opened
			System.out.println("The file " + file + " was not found.");
		}
		
	} //readPayrollInfo
	
	/**
	 * Returns the number of employees who worked over 40 hours;  the helper method overtime is called to do all the work.
	 * @return number of employees who worked over 40 hours.
	 */
	public int numOvertime() {
		return overtime(0);
	}
	
	/**
	 * Returns the number of employees in the part of the list from index start to the end who worked more than 40 hours.  This value is calculated recursively.
	 * @param start The index of the starting position in the list
	 * @return The number of employees in the part of the list from the index start to the end who worked more than 40 hours.
	 */
	private int overtime(int start) {
		int numOvertimeWorkers = 0;

		//make sure the start position is a valid index in the payroll array
		if (start >= 0 && start < MAX && payroll[start] != null) {

			//System.out.println(start); //debugging
		 	
			//handle the base case here: get the employee at the start index and determine overtime status
			Employee laborer = payroll[start];
			
			//if this employee worked overtime, add to the counter
			if (laborer.hours > 40) {
				numOvertimeWorkers++;
			}			
			
			//handle the rest recursively: calculate how many of the rest of the employees worked overtime
			numOvertimeWorkers += overtime(start + 1);
		}
		
		return numOvertimeWorkers;
	}

}

Overtime.java

package edu.nyu.cs.fb1258;

import java.util.Scanner;

/**
 * Test class to read payroll data and output how many employees worked overtime.
 * @author Foo Barstein
 * @version 2
 *
 */
public class Overtime {

	public static void main(String[] args) {
		String filename;		//Name of the file containing employee data
		int numOvertimeWorkers; //Number of workers who worked overtime

		Scanner scn = new Scanner(System.in);
		
		System.out.println("\nPayroll Program");
		System.out.print("Enter the name of the file containing payroll data: ");

		//get the name of the file from the user
		filename = scn.nextLine();
		
		//instantiate a Payroll object
		Payroll p = new Payroll();
		
		//read in the data from the file
		p.readPayrollInfo("src/" + filename);
		
		//if the payroll data has been read, analyze the data
		if (p.hasData) {
			//Print the number of workers who worked overtime.
			numOvertimeWorkers = p.numOvertime();
			System.out.println(numOvertimeWorkers + " workers worked overtime.");		
		}
		
		//close the file
		scn.close();
	}
}

Data files

payroll1.txt

A valid data file that can be read by the program:

Smith 45 13.50
Jones 39 23.75
Doe 40 17.80
Moe 30 21.90
Walker 41 14.60
Walton 57 8.95
Taylor 40 16.75
Lewis 40 35.50
Abbott 43 12.70
Who 39 33.95
Herrod 21 19.90
James 49 13.50
Summers 40 20.00
Winter 40 18.75
Farthington 38 24.50
Walsh 42 45.70

payroll2.txt

Another smaller sample data file that can be read by the program:

Jones 40 9.75
Ricardo 35 13.69
Smith 40 20.00
Smythe 40 17.80

Additional challenge

Try to create a recursive method that calculates the total cost of all overtime work. This will be very similar to how the number of overtime workers are calculated.

What links here