Knuth Numbers recursion

[Miriam]

Hello,

I recently had a final exam on which my teacher asked to write a method for Knuth numbers recursion. I got a stack overflow on my implementation, and I am new on Java, so I am not sure what happened, it might be that I had the wrong formula for Knuth numbers? I would love some feedback.

Here is the question, and my code

Knuth numbers are given by the recursive formula Kn+1 = 1 + min (2 * Ka, 3 * Kb) where a is the smallest integer larger than n/2.0 and b is the smallest integer larger than n/3.0. The use of doubles in the denominator is necessary to ensure that integer division is not used.

For example, if n is 7, then a equals 4 and b equals 3 and thus K8 = 1 + min (2* K4, 3 * K3).

If n is 8, then a equals 5 while b remains 3 and thus K9 = 1 + min (2 * K5, 3 * K3).
If n is 9, then a remains 5 while b equals 4 and thus K10 = 1 + min(2 * K5, 3 * K3).

Mathematically, “the smallest integer larger than x” is the “ceiling” function. If n is an int, then n / 2 is calculated using integer division, discarding the remainder; but you want the division to give you a double. Thus you need code that looks like this:

int a = Math.ceil(n / 2.0);
int b = Math.ceil(n / 3.0);

Since the equation defining Knuth numbers is a recursive one, we must have a base case; let’s assume that K0 = 1.

Create and test a class called KnuthNumbers (in a project also called KnuthNumbers) which includes a static method to compute Knuth numbers.

my code:

Code:

public class KnuthNumbers
{
   /**
    * Recursive Knuth Numbers 1, 3, 3, 4, 7, 7, 7, 9, 9, 10, 13, ...  
    */
   public static int knuthNumber(final double n)
   throws DataFormatException{
       double a = Math.ceil(n / 2.0);
       double b = Math.ceil(n / 3.0);
       // bad input
       if (n < 1)
           throw new DataFormatException("n cannot be less then 1");
       if (n > 12)
           throw new DataFormatException("n is too large. Max is 12");
       //base case
       if (n == 1)
           return 1;

       //recursion

       return knuthNumber(a + b);
   }
}

TEST:

Code:

public class KnuthNumbersTest
{
   

   @Test
   public void testKnuthNumber(){
       long startTime = 0;
       long endTime = 0;
       double result = 0;

       try {
           assertEquals(-1, KnuthNumbers.knuthNumber(-3));
           fail("number should not be negative");
       }
       catch (DataFormatException e){
           assertEquals("n cannot be less then 1", e.getMessage());
       }
       catch (Exception e) {
           fail("Unexpected exception: " + e.toString());
       }

       try {
           assertEquals(0, KnuthNumbers.knuthNumber(0));
           fail("number should not be zero");
       }
       catch (DataFormatException e){
           assertEquals("n cannot be less then 1", e.getMessage());
       }
       catch (Exception e) {
           fail("Unexpected exception: " + e.toString());
       }

       try {
           assertEquals(1, KnuthNumbers.knuthNumber(1.0));
           assertEquals(9, KnuthNumbers.knuthNumber(5.4));
           assertEquals(13, KnuthNumbers.knuthNumber(7.6));
       }
       catch (Exception e) {
           fail ("Unexpected exception: " + e.toString());
       }

   }

}