Chapter 10: "Recursion"

Data Structures with Java, Rick Mercer

Answers to Self-Check Questions


10-1 powRecurse (3, 0) == 1

10-2 powRecurse (3, 1) == 3
	
10-3 – filled in from top to bottom
		3*(3, 0) = 1
		3*(3, 1) = 3*1 = 3
		3*(3, 2) = 3*3 = 9
		3*(3, 3) = 3*9 = 27
		3*(3, 4) = 3*27 = 81
	 
10-4 result mystery(5)
	    1 <2> 1 <3> 1 <2> 1 <4> 1 <2> 1 <3> 1 <2> 1 <5> 1 <2> 1 <3> 1 <2> 1 <4> 1 <2> 1 <3> 1 <2> 1 
	   	fence post pattern - the brackets follow the numbers being recursed back into the method
	
10-5 mystery2(4) result: 1 2 3 4 
	
10-6 return values mystery6, in order
	  0
	  1
	  2
	  4
	  8

10-7 return values mystery7, in order
	  false
	  false
	  true

10-8 fibonacci

	public int fibonacci(int term){
		if(term == 0)
			return 1;
		else if(term ==1)
			return 1;
		else if(term >= 2)
			return fibonacci(n-1) + fibonacci(n-2);
		else
			return -1;
	}
	
10-9 add stack

	public int asStack(OurStack <Integers> nums){
		int sum = 0;
		int temp = 0;
		OurStack<Integers> tempNums = new OurLinkedStack<Integers>();
		
		return sumHelper(nums, sum, temp, tempNums);
	}

	private int sumHelper(OurStack<Integers> nums, int sum, int temp, OurStack 			tempNums) {
		
		if(nums.isEmpty)
			while(!tempNums.isEmpty)
				nums.push(tempNums.pop());
			return sum;
		else 
			int temp = nums.peek();
			tempNums.push(nums.pop());
			return sumHelper (nums, sum + temp, temp, tempNums)
		} 

	
10-10 isPalendrome("yoy") == true

10-11 isPalendrome("yoyo") == false
	
10-12 return values for huh, in order
	  +abc+
	  abc
	  a-b-c
	  abc
	
10-13 - if "Kelly" is not found at the first index, it will throw an arrayIndexOutOfBounds exception

10-14 - it will immediately return false without searching
	
10-15 printForward method
	
	public void printForward(Object[] array, int n){
		String str="";
		printForwardHelper(array, n, 0, str);
	}

	private void printForwardHelper(Object[] array, int n, int tracker, String str) {
		if(tracker>=n)
			System.out.println(str);
		else
			printForwardHelper(array, n, tracker+1, str + array[tracker]+" ");
	}

10-16 reverse tester method

	public void printReverse(Object[] array, int leftIndex, int rightIndex)

    public void testReverse() {
      String[] array = {"A", "B", "C" };
      reverse(array, 0, 2);  

      assertEquals("A", array[2]);
      assertEquals("B", array[1]);
      assertEquals("C", array[0]);
    }
	
10-17 reverse method

	public void reverse(Object[] array, int leftIndex, int rightIndex){
		reverseHelp(array, leftIndex, rightIndex, temp);
	}
	
	private void reverseHelp(Object[] array, int leftIndex, int rightIndex, Object temp){
		if((array.lenght%2 != 0 && leftIndex < (((array.length-1)/2)+(array.length%2)) && rightIndex > ((array.length-1)/2+((array.length-1)%2))) 
			||(array.length%2 == 0 && leftIndex <= (((array.length-1)/2)+(array.length%2)) && rightIndex > ((array.length-1)/2+((array.length-1)%2))) )
			temp = array[leftIndex];
			array[leftIndex] = array[rightIndex];
			array[rightIndex] = temp;
			reverseHelp(array, leftIndex+1, rightIndex-1, temp);
		}
	}
	
10-18 toString for SimpleLinkedList

	public String toString (){
		String str = "";
		Node ref = front;
		return toStringHelper(str, ref);
	}

	private String toStringHelper(String str, Node ref) {
		if(ref == null)
			return str;
		else if (ref.next == null)
			return str;
		else
			return str + ref.data + " " + toStringHelper(str, ref.next);
	}