Consider the following recursive method:

   /**
    * Returns the string made up of the characters in s starting
    * from index idx and going to the end of s. For
    * example,
    * 
    * endOf("abcdef", 0) returns "abcdef"
    * endOf("abcdef", 1) returns "bcdef"
    * endOf("abcdef", 2) returns "cdef"
    * endOf("abcdef", 3) returns "def"
    * 
    * An empty string is returned if idx is greater than or equal to
    * the length of s.
    * 
    * @param s
    *          a string
    * @param idx
    *          the starting index in s
    * @pre. idx >= 0
    * @return the string made up of the characters in s starting from index idx
    *         and going to the end of s
    */
   public static String endOf(String s, int idx) {
     String result = "";
     if (idx >= s.length()) {
       result = "";
     }
     else {
       result = s.charAt(idx) + endOf(s, idx + 1);
     }
     return result;
   }

Prove that the method endOf is correct using the approach from the lectures (i.e., prove that the base cases are correct and that the recursive case of the method is correct).

First prove the correctness of the base case(s).

Base case: If idx is greater than or equal to the length of s, then the empty string is returned, which is correct (as this is stated explicitly as a postcondition in the method API).

Next assume that the recursive invocation(s) are correct and prove under that assumption that the recursive case is correct as well.

Recursive case: Assume that endOf(s, idx + 1) returns the string made up of the characters in s starting from index (idx + 1) and going to the end of s. We know that idx is a valid index for the string s because the precondition ensures that idx is not negative, and the base case ensures that idx is less than the length of s. The method returns the string made up of the character at index idx followed by all of the characters after index idx up to the end of s.

Prove that the method endOf (from part A) terminates using the approach from the lectures.

First define the size of the problem.

Size of endOf(s, idx): Define the size to be n = (s.length() - idx) or 0, whichever is greater. The length of a string is an integer greater than or equal to zero; therefore, n is a natural number.

Next prove each recursive invocation has a smaller size than the original invocation.

Recursive case: The size of endOf(s, idx + 1)) is equal to (s.length() - (idx + 1)) = (s.length() - idx - 1) = (n - 1) which is less than n.

The size of the recursive invocation is less than n; therefore, the method terminates.

State the recurrence relation for the method endOf (from part A). Make sure to include the recurrence relation for the base case. The exact value of any constants that appear in the recurrence relation are unimportant.

The base case occurs when (s.length() - idx) is less than or equal to zero. Using our definition of the size of the problem from Part B, the base case occurs when n = 0. When the base case runs, we have the declaration and assignment of result, the assignment of result (again which is unnecessary), followed by a return statement; therefore, we have:

T(0) = 4

When the recursive case runs, endOf(s, idx + 1) has size (n - 1) which requires T(n - 1) number of elementary operations. Counting up all of the other elementary operations required when the recursive case runs leads to some constant number; therefore, we have:

T(n) = T(n - 1) + constant

Note that the explanation is not required as part of the answer.