• Home Page
  • Recursive Programs

    "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:

    Learn more about recursion.
              
                // 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;
    	}
    }