Homework: Recursion I

For each of the following problems, you need to find a recursive solution. For problems involving NaturalNumber, use only the kernel methods. Do not use "tricks" like converting a NaturalNumber into a String and then solving the problem on the String.

1. Implement the static method declared as follows:

   /**
    * Returns the number of digits of {@code n}.
    * 
    * @param n
    *            {@code NaturalNumber} whose digits to count
    * @return the number of digits of {@code n}
    * @ensures numberOfDigits = [number of digits of n]
    */
   private static int numberOfDigits(NaturalNumber n) {...}
   

2. Implement the static method declared as follows:

   /**
    * Returns the sum of the digits of {@code n}.
    * 
    * @param n
    *            {@code NaturalNumber} whose digits to add
    * @return the sum of the digits of {@code n}
    * @ensures sumOfDigits = [sum of the digits of n]
    */
   private static int sumOfDigits(NaturalNumber n) {...}
   

3. In addition to the kernel methods, for this question (only!) you are allowed to use the NaturalNumber method add. Implement the static method declared as follows:

   /**
    * Returns the sum of the digits of {@code n}.
    * 
    * @param n
    *            {@code NaturalNumber} whose digits to add
    * @return the sum of the digits of {@code n}
    * @ensures sumOfDigits = [sum of the digits of n]
    */
   private static NaturalNumber sumOfDigits(NaturalNumber n) {...}
   

4. Implement the static method declared as follows:

   /**
    * Divides {@code n} by 2.
    * 
    * @param n
    *            {@code NaturalNumber} to be divided
    * @updates n
    * @ensures 2 * n <= #n < 2 * (n + 1)
    */
   private static void divideBy2(NaturalNumber n) {...}
   

5. Implement the static method declared as follows:

   /**
    * Checks whether a {@code String} is a palindrome.
    * 
    * @param s
    *            {@code String} to be checked
    * @return true if {@code s} is a palindrome, false otherwise
    * @ensures isPalindrome = (s = rev(s))
    */
   private static boolean isPalindrome(String s) {...}