One method requires you to devise a recursive solution, another requires converting a recursive method into a tail-recursive form, and the third requires converting a recursive function into an iterative function with an explicit stack. Each method has a TODO comment above explaining it explaining what you need to write. There are tests for each method and if you all the tests pass, you will get full credit. Note, however, that if you write the method in a style/form other than the one required (IE you create a recursive method when the instructions requested an iterative method), you will receive 0 points for that method.

Factorial.java ---------------- public class Factorial { public static int factorialRecursive(int n) { if (n == 1 || n == 0) { return 1; } return n * factorialRecursive(n - 1); } public static int factorialTailRecursive(int n) { return factorialTailRecursive(n, 1); } // TODO: Rewrite factorialRecursive as a tail-call recursive function. To review, that means // the return statement for the recursive case should contain only a function and no // other operations. The accumulator argument for the function is already set up for you. public static int factorialTailRecursive(int n, int accum) { return 0; } }

--------------------

LinkedList.java

---------------------

public class LinkedList { static class Node { int data; Node next; } Node node; private int size() { int i = 0; Node n = this.node; while (n != null) { i += 1; n = n.next; } return i; } public int[] toArray() { int[] array = new int[this.size()]; int i = 0; Node n = this.node; while (n != null) { array[i] = n.data; i += 1; n = n.next; } return array; } static public LinkedList fromArray(int[] array) { Node n = null; for (int i = array.length - 1; i >= 0; i--) { Node newNode = new Node(); newNode.data = array[i]; newNode.next = n; n = newNode; } LinkedList list = new LinkedList(); list.node = n; return list; } // TODO: Write a recursive function to combine two sorted linked lists into a new // sorted linked list. This is just like the combine function we went over in // class for the merge sort example, except it operates over linked lists instead // of arrays. private static Node combineRecursive(Node first, Node second) { return null; } public LinkedList combineSorted(LinkedList other) { LinkedList ret = new LinkedList(); ret.node = combineRecursive(this.node, other.node); return ret; } } 

-------------------

Permutation.java

--------------------

import java.util.Arrays; public class Permutation { private static void swap(Object[] array, int a, int b) { Object tmp = array[a]; array[a] = array[b]; array[b] = tmp; } public static void printPermutationsRecursive(Object[] array) { printPermutationsRecursive(array, 0); } private static void printPermutationsRecursive(Object[] array, int i) { if (i == array.length - 1) { System.out.println(Arrays.toString(array)); } else { for (int k = i; k < array.length; k++) { swap(array, i, k); printPermutationsRecursive(array, i + 1); swap(array, i, k); } } } // TODO: Rewrite printPermutationsRecursive into an iterative form using an explicit stack. // This will likely require making an inner class like we did with the merge-sort // example in class. The source code for that example is available on blackboard if // you would like to review it. public static void printPermutationsIterative(Object[] array) { } }