CSC236 Data Structures - Problem Set: Recursion

Problem Set: Recursion

What output does the following program produce?

public class theValue {
    public static void main(String[] args) {
        System.out.println(theVal(1,7,7));
    }

    public static int theVal(int A, int B, int N) {
        int returnVal;

        System.out.println("Enter: A = " + A + " B = " + B);
        int C = (A + B ) / 2;
        if (C * C <= N)
            returnVal = C;
        else
            returnVal = theVal(A, C-1, N);

        System.out.println("Leave: A = " + A + " B = " + B);
        return returnVal;
    }
}

What output does the following program produce?

public class RecursionTest {
    public static void main(String[] args) {

        R(5,3);
    }

    static void R(int X, int Y) {
        if (Y > 0) {
            X++;
            Y--;
            System.out.println(X + "  " + Y);
            R(X,Y);
            System.out.println(X + "  " + Y);
        }
    }
}

What output does the following program produce?

public class RecursionTest {
    public static void main(String[] args) {
        System.out.println(f(6,8));
    }

    public static int f(int k, int n) {
        if (n == k)
            return k;
        else
            if (n > k)
                return f(k,n-k);
            else
                return f(k-n,n);
    }
}

What output does the following program produce? What argument values, if any, could you pass to F that would cause the program to run forever?

public class RecursionTest {
    public static void main(String[] args) {

        System.out.println("F(8) = " + F(8));
    }

    static int F(int N) {
        System.out.println("F entered with N = " + N);
        if (N >= 0 && N <= 2) {
            return N+1;
        }
        else {
            return F(N-2) * F(N-4);
        }
    }
}

Write a recursive function that will compute the sum of the first N integers in an array of at least N integers. (Hint: begin with the Nth integer.)
Given an integer N > 0, write a recursive function that writes the integers 1, 2, ..., N.
Write a recursive function writeLine that writes a character repeatedly to form a line of n characters. For example, writeLine('*',5) writes the line *****.
Write a recursive function writeBlock that uses writeLine to write m lines of n characters each. For example, writeBlock('*',5,3) produces the output:
```
   *****
   *****
   *****
```
Perform a box trace of the recursive binary search function with the array containing the values 1, 5, 9, 12, 15, 21, 29, 31 when searching for each of the following values:
1. 5
2. 13
3. 16
Imagine that you have 101 dalmations and that no two dalmatians have the same number of spots. Suppose that you create an array of 101 integers: the first integer is the number of spots on the first dalmatian, the second integer is the number of spots on the second dalmatian, and so on. Your friend wants to know whether you have a dalmatian with 99 spots. Thus you need to determine whether your array contains the integer 99.
1. If you plan to use binary search to look for the number 99, what do you need to do to the array before you search it?
2. What is the index (subscript) of the integer in the array that binary search would check first?
3. If all your dalmatians have more than 99 spots, how many comparisons will the binary search require to determine that 99 is not in the array?
Write a recursive function numevens(LLNode<Integer> list) to count and return the number of even numbers in a linked list of Integers.
Write a recursive function contains(int target, LLNode<Integer> list) that returns true if target is found in list, and returns false if target is not found in list.

public static boolean paltest(String str) {
   boolean result = false;
   if (str.length() <= 1)
      result = true;
   else {
      if (str.charAt(0) == str.charAt(str.length()-1))
         result = paltest(str.substring(1,str.length()-1));
   }
   return result;
}

Trace the following call to paltest and tell what is returned:
```
     paltest("abcba");
```
Trace the following call to paltest and tell what is returned:
```
     paltest("abcxycba");
```

static void prback(LLNode<String> head) {
   if (head == null)
      return;
   else {
      prback(head.getLink());
      System.out.println(head.getInfo());
   }
}

Trace prback and show what is printed if head points to the following list:

Write a recursive function to perform a linear search of an array of ints: given an array of ints and an int value, search the array for value. Return -1 if value is not found, otherwise return the subscript where value is found.
Write a recursive function to count and return the number of even numbers in an array of ints.
Write a recursive function to perform a linear search of an array of ints: given an array of ints and an int value, search the array for value. Return -1 if value is not found, otherwise return the subscript where value is found.
Write a recursive function to reverse a String. For example, if the function is called with the String "winter is coming", it should return "gnimoc si retniw".