CSC-220 Recusrve Examples Code

RecursiveExamples.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

public class RecursiveExamples {
	//====================================================================
	public static int factIterative(int num) {
		int ans = 1;
		for (int i= 1; i < num; i++) 
			ans *= i;
		return ans;
	}
	
	//====================================================================
	public static int fact(int num)
	{
	   if (num == 0)
	      return 1;
	   else
	      return num * fact(num - 1);
	}
	
	//====================================================================
	private static int factTail(int num, int retval) {
		if (num == 0)
			return retval;
		return factTail(num - 1, num * retval);
	}
	
	public static int factTail(int num) {
		return factTail(num, 1);
	}

	//====================================================================
	
	private static boolean isPerfectIterative(int number) {
		int sum = 0;
		for (int fact = 1; fact <= number - 1; fact++)
			if (number % fact == 0)
				sum += fact;
		return number == sum;
	}

	private static int sumOfFactors(int number, int fact) {
		if (fact == number)
			return 0;
		if (number % fact == 0)
			return fact + sumOfFactors(number, fact + 1);
		return sumOfFactors(number, fact + 1);
	}

	public static boolean isPerfect(int number) {
		return number == sumOfFactors(number, 1);
	}

	//====================================================================
	private static int gcdIterative(int m, int n) {
		m = Math.abs(m);
		n = Math.abs(n);
		while (n != 0) {
			int next = m % n;
			m = n;
			n = next;
		}
		return m;
	}
	
	private static int gcd(int m, int n) {
		if (n == 0)
			return m;
		return gcd(n, m % n);
	}
	
	//====================================================================
	private static void forwardPrint(int list[], int n) {
		if (n < list.length) {
			System.out.println(list[n]);
			forwardPrint(list, n + 1);
		}
	}
	
	public static void forwardPrint(int list[]) {
		forwardPrint(list, 0);
	}
	
	//====================================================================
	
	private static void revPrint(int list[], int n) {
		if (n < list.length) {
			revPrint(list, n + 1);
			System.out.println(list[n]);
		}
	}
	
	public static void revPrint(int list[]) {
		revPrint(list, 0);
	}
	
	//====================================================================

	private static int[] revArray(int list[], int index) {
		if (index >= list.length)
			return new int[] {};
		int temp[] = revArray(list, index + 1);
		int retval[] = new int[temp.length + 1];
		System.arraycopy(temp, 0, retval, 0, temp.length);
		retval[retval.length - 1] = list[index];
		return retval;		
	}

	public static int[] revArray(int list[]) {
		return revArray(list, 0);
	}
	
	//====================================================================

	private static ArrayList<Integer> revArrayList(ArrayList<Integer> list, int index) {
		if (index >= list.size())
			return new ArrayList<>();
		ArrayList<Integer> temp = revArrayList(list, index + 1);
		temp.add(list.get(index));
		return temp;	
	}
	
	public static ArrayList<Integer> revArrayList(ArrayList<Integer> list) {
		return revArrayList(list, 0);
	}

	//====================================================================
	private static int mult(int list[], int n) {
		if (n >= list.length)
			return 1;
		else
			return list[n] * mult(list, n + 1);
	}
	
	public static int mult(int list[]) {
		return mult(list, 0);
	}
	
	//====================================================================
	private static int largest(int list[], int n) {
	   if(n == list.length - 1)
	      return list[n];
	   else {
	     int max = largest(list, n + 1);
	   	 return list[n] > max ? list[n] : max;
	   }
	}
	
	public static int largest(int list[]) {
		return largest(list, 0);
	}
	
	//====================================================================
	private static int fib(int a, int b, int n) {
	    if(n == 0)
	       return a;
	    else if(n == 1)
	       return b;
	    else
	       return fib(b, a + b, n - 1);
	}
	
	public static int fib(int n) {
		return fib(0, 1, n);		
	}
	
	private static int fib2(int n) {
	    if(n == 0 || n == 1)
	       return n;
	    else
	       return fib2(n - 1) + fib2(n - 2);
	}

	
	//====================================================================
	private static void dec2BinHelper(int x, int base) {
		if (x < 0) {
			System.out.print("-");
			dec2BinHelper(-x, base);
		}
		else if (x > 0) {
			dec2BinHelper(x / base, base);
			System.out.print(x % base);
		}
	}

	//====================================================================
	public static void dec2Bin(int x, int base) {
		if (x == 0)
			System.out.print("0");
		else 
			dec2BinHelper(x, base);
		System.out.println();
	}
	
	private static String dec2BinHelper2(int x, int base) {
		if (x < 0) {
			return "-" + dec2BinHelper2(-x, base);
		}
		else if (x > 0) {
			return dec2BinHelper2(x / base, base) + (x % base);
		}
		return "";
	}

	public static String dec2Bin2(int x, int base) {
		if (x == 0)
			return "0";
		else 
			return dec2BinHelper2(x, base);
	}
		
	//====================================================================
	
	private static void hanoi(int count, int source, int dest, int temp) {
		if (count > 0) {
			hanoi(count - 1, source, temp, dest);
			System.out.println("Move disk " + count + " from " + source + 
			                   " to " + dest);
			hanoi(count - 1, temp, dest, source);
		}
	}
	
	public static String hanoi2(int count, int source, int dest, int temp) {
		if (count > 0) {
			String retval = "";
			retval += hanoi2(count - 1, source, temp, dest);
			retval += "Move disk " + count + " from " + source + " to " + dest + "\n";
			retval += hanoi2(count - 1, temp, dest, source);
			return retval;
		}
		return "";
	}
	
	public static ArrayList<String> hanoi3(int count, int source, int dest, int temp) {
		if (count > 0) {
			ArrayList<String> retval;
			retval = hanoi3(count - 1, source, temp, dest);
			retval.add("Move disk " + count + " from " + source + " to " + dest);
			retval.addAll(hanoi3(count -1, temp, dest, source));
			return retval;
		}
		return new ArrayList<>();
	}

	//====================================================================

	public static double power(double base, int exp) {
		if (exp < 0)
			return 1.0 / power(base, -exp);
		if (exp == 0)
			return 1.0;
		else
			return base * power(base, exp - 1);
	}
	
	public static void main(String args[]) {

	}
	
	public static void mainyyy(String args[]) {
		int list[] = { 768, 4, 6, 8, 313, 12, -7 };
		System.out.println(Arrays.toString(revArray(list)));
		ArrayList<Integer> list2 = new ArrayList<>();
		for (int item: list)
			list2.add(item);
		ArrayList<Integer> revList2 = revArrayList(list2);
		System.out.println(Arrays.toString(revList2.toArray()));
	}

	public static void mainxxx(String args[]) {
		//int list[] = { 768, 4, 6, 8, 313, 12, -7 };
		//System.out.println(largest(list));
		//System.out.println(mult(list));
		//System.out.println(dec2Bin2(12345, 10));
		
		// Hanoi V1
		System.out.println("Classic Hanoi");
		hanoi(4, 1, 3, 2);
		System.out.println();	
		
		// Hanoi V2
		System.out.println("Hanoi that Returns String Text of Moves");
		System.out.println(hanoi2(4, 1, 3, 2));
		System.out.println();	
		
		// Hanoi V3
		System.out.println("Hanoi that returns ArrayList of Moves");
		System.out.println("Demos 2 types of iterations");
		ArrayList<String> hanoi = hanoi3(4, 1, 3, 2);
		Iterator<String> it = hanoi.iterator();
		while (it.hasNext()) {
			String move = it.next();
			System.out.println(move);
		}
		System.out.println();
		for (String s : hanoi) {
			System.out.println(s);
		}
		
	}

}