"Recursive Programs" is a project that I did involving a number of recursive Java programs. The project demonstrates a few various recursive algorithms. Here's a brief description of what each program does:
// Java code for the Recursive Programs
import java.util.ArrayList;
import java.util.Arrays;
public class Recursion {
//How many subsets are there of the numbers 1...n
// that don't contain any consecutive integers?
public static long nonConsecutiveSubsets(int n)
{
if (n == 0)
{
return 1;
}
if (n == -1)
{
return 1;
}
return nonConsecutiveSubsets(n-1) + nonConsecutiveSubsets(n-2);
}
//A kid at the bottom of the stairs can jump up 1, 2, or 3 stairs at a time.
//How many different ways can they jump up n stairs?
// Jumping 1-1-2 is considered different than jumping 1-2-1
public static long waysToJumpUpStairs(int n)
{
if (n == 1 || n == 0)
{
return 1;
}
if (n == -1)
{
return 0;
}
return (waysToJumpUpStairs(n-1) + waysToJumpUpStairs(n-2) + waysToJumpUpStairs(n-3));
}
//Prints the value of every node in the singly linked list with the given head, but in reverse
public static void reverseList(ListNode head)
{
if (head == null)
{
return;
}
reverseList(head.getNext());
System.out.println (head.getValue());
}
//For the given 2D array of Strings, replaces the String at index[x][y]
//with "infected" unless the String is "vaccinated";
// also, any Strings they are orthogonally adjacent to
//that are not "vaccinated" will also be infected, and any adjacent to
//them as well etc.
public static void infect(String[][] grid, int x, int y)
{
if (x < 0 || y < 0 || y > grid.length || x > grid[0].length || grid[x][y].equals("vaccinated") || grid[x][y].equals("infected"))
{
return;
}
grid[x][y] = "infected";
if (x == 0)
{
infect(grid, x, y-1);
infect(grid, x, y+1);
infect(grid, x+1, y);
return;
}
else if (x == grid.length - 1)
{
infect(grid, x, y-1);
infect(grid, x, y+1);
infect(grid, x-1, y);
}
else if (y == 0)
{
infect(grid, x, y+1);
infect(grid, x-1, y);
infect(grid, x+1, y);
}
else if (y == grid.length - 1)
{
infect(grid, x, y-1);
infect(grid, x-1, y);
infect(grid, x+1, y);
}
else
{
infect(grid, x, y-1);
infect(grid, x, y+1);
infect(grid, x-1, y);
infect(grid, x+1, y);
}
}
//List contains a single String to start.
//Prints all the permutations of str on separate lines
//You may assume that str has no repeated characters
//Order is your choice
public static void permute(String str)
{
permutation("", str);
}
private static void permutation(String prefix, String str)
{
int len = str.length();
if (len == 0)
{
System.out.println(prefix);
}
for (int i = 0; i < len; i++)
{
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, len));
}
}
//takes two objects and returns one string that is the concatenated version of the two objects
public static String mergeString (Object obj1, Object obj2)
{
String ans = "" + obj1 + obj2;
return ans;
}
//Prints all the subsets of str on separate lines
//You may assume that str has no repeated characters
//For example, subsets("abc") would print out "", "a", "b", "c", "ab", "ac", "bc", "abc"
//Order is your choice
public static void subsets(String str)
{
String[] ans = subArrays(str);
for (int i = 0; i < ans.length; i++)
{
System.out.println (ans[i]);
}
}
public static String[] subArrays (String str)
{
String[] empty = {""};
if (str.length () == 0)
{
return empty;
}
String[] subAns = subArrays (str.substring(1));
String[] ans = new String[subAns.length * 2];
int index = 0;
for (int i = 0; i < subAns.length; i++)
{
ans[index] = str.charAt(0) + subAns[i];
index++;
}
for (int i = 0; i < subAns.length; i++)
{
ans[index] = subAns[i];
index++;
}
return ans;
}
//Performs a mergeSort on the given array of ints
public static void mergeSort(int[] ints)
{
//don't have to do this but if there's time...
}
public static int findLow (int[] input)
{
int tempLow = input[0];
for (int i = 0; i < input.length; i++)
{
if (input[i] <= tempLow)
{
tempLow = input[i];
}
}
return tempLow;
}
public static int findHigh (int[] input)
{
int tempHigh = input[0];
for (int i = 0; i < input.length; i++)
{
if (input[i] >= tempHigh)
{
tempHigh = input[i];
}
}
return tempHigh;
}
//swaps elements
public static void swapEles (int[] arr, int pos1, int pos2)
{
int temp = pos1;
arr[pos1] = arr[pos2];
arr[pos2] = arr[temp];
}
//Performs a quickSort on the given array of ints
//Use the middle element (index n/2) as the pivot
public static void quickSort(int[] ints)
{
quickSort2 (ints, 0, ints.length - 1);
}
//the same thing as quicksort just better.
public static void quickSort2 (int[] ints, int low, int high)
{
if (low < high)
{
int partIndex = partition(ints, low, high);
quickSort2(ints, low, partIndex - 1);
quickSort2(ints, partIndex + 1, high);
}
}
//does the swaps for the particular spots
public static int partition(int arr[], int start, int end)
{
int pivot = arr[end];
int i = (start-1);
for (int j = start; j < end; j++)
{
if (arr[j] <= pivot)
{
i++;
int swapTemp = arr[i];
arr[i] = arr[j];
arr[j] = swapTemp;
}
}
int swapTemp = arr[i+1];
arr[i+1] = arr[end];
arr[end] = swapTemp;
return i+1;
}
//Prints a sequence of moves (one on each line)
// to complete a Towers of Hanoi problem with
//n disks starting on tower 0, ending on tower 1.
// The towers are number 0, 1, 2, and each move should be of
//the form "1 -> 2", meaning "take the top disk of tower 1 and
//put it on tower 2" etc.
public static void solveHanoi(int n)
{
System.out.println (solveHanoiBetter (n, 0, 1));
}
//prints the sequence just like solveHanoi should.
public static String solveHanoiBetter (int n, int from, int to)
{
if (n == 0)
{
return null;
}
if (n == 1)
{
return (from + " -> " + to);
}
String step1;
String step2;
String step3;
int other = 3 - from - to;
step1 = solveHanoiBetter (n - 1, from, other);
step2 = from + " -> " + to;
step3 = solveHanoiBetter (n-1, other, to);
return step1 + "\n" + step2 + "\n" + step3;
}
// You are partaking in a scavenger hunt!
// You've gotten a secret map to find many of the more difficult
// items, but they are only available at VERY specific times at
// specific places. You have an array, times[], that lists at which
// MINUTE an item is available.
// Items in the ScavHunt are worth varying numbers of points.
// You also have an array, points[], same length as times[],
// that lists how many points each of the corresponding items is worth.
// Problem is: to get from one location to the other takes 5 minutes,
// so if there is an item, for example, available at time 23 and another
// at time 27, it's just not possible for you to make it to both: you'll
// have to choose!
// (but you COULD make it from a place at time 23 to another at time 28)
// Write a method that returns the maximum POINTS you can get.
public static int scavHunt(int[] times, int[] points)
{
return scavHuntHelper (times,points, 0);
}
private static int scavHuntHelper (int[] times, int[] points, int startIndex)
{
if (startIndex >= times.length)
{
return 0;
}
int next = nextNonConflicting (times, startIndex);
return Math.max((scavHuntHelper(times, points, startIndex + 1)), points[startIndex] + scavHuntHelper (times, points, next));
}
private static int nextNonConflicting (int[] times, int startIndex)
{
for (int i = startIndex; i < times.length; i++)
{
if (times[i] >= times[startIndex] + 5)
{
return i;
}
}
return times.length;
}
}