Recursion and While Loops in Java

Question

I'm writing a recursive program:

public static List method(int n)

to determine whether a positive number n is the total of cubes that are positive (> 0). Example: given n = 1944 (12^3 + 6^3), the program would return the list [12, 6] in descending order. If n is not the total of cubes the program should return an empty list.

The program should return the values that start with the highest possible value for the first element, and then follow the same rule for the rest of the elements. For example, when n = 1072, the program would return [10, 4, 2] instead of [9, 7].

The method where the recursion should occur:

private static boolean method(int n, int c, LinkedList seen)

where c is the highest number that is still allowed to be used and soFar is the list of numbers that have already been seen.

My code covers the base cases and the recursion, but I'm having issues with the loop continuing. With the input, n = 1944 my program is returning the list [12] instead of [12, 6].

    public static List method(int n)
    {
        LinkedList result = new LinkedList();
        int c = (int) Math.cbrt(n);
        result.add(c);
        method(n, c, result);
        return result;
    }
    private static boolean method(int n, int c, LinkedList seen)
    {
        LinkedList result = new LinkedList();
        boolean b = false;
        if (n == 0)
        {
          return true;  
        }
        else if (c == 0)
        {
            return false;
        }
        else 
        {
            int sum = 0;
            for (int i : seen)
            {
                sum += i*i*i;
            }
            while (b = false)
            {
                c = (int) Math.cbrt(n - sum);
                seen.add(c);
                method(n, c, seen);
                if (sum == n)
                {
                    result = seen;
                    return true;
                }
                else
                {
                    return false;
                }
            }
        }
        return false;
    }

Victor Stafusa · Accepted Answer

Let's see your while loop:

LinkedList result = new LinkedList();
boolean b = false;
// Some code omitted here.
while (b = false)
{
    c = (int) Math.cbrt(n - sum);
    seen.add(c);
    method(n, c, seen);
    if (sum == n)
    {
        result = seen;
        return true;
    }
    else
    {
        return false;
    }
}

First, with a while loop that always has false as the condition for looping, it doesn't do anything at all.

Anyway, even if we pretend the loop runs, whatever is the branch took by the if, a return will be reached. So, your while loop doesn't loop at all even if its condition was changed to always be true. Further, the only value ever assigned for the b variable is false, and it isn't used for anything at all.

Also, the result list in the second method is always empty. And, since the result = seen; instruction is just right before the return, it is an innocuous instruction which renders the result simply being useless.

Also, look at the method(n, c, seen); call. It don't do anything with its return value! So, even if it eventually returns true, you still proceeds, which would then generate false as a result.

Also, whenever you add a value to seen, it will never be removed. Since the seen is always the very same list in every of the recursive method calls, once a bad number is added there, it will never be removed to make the way for something else.

With this, I must conclude that your algorithm is so broken that it must be rewritten from scratch.

Also, although your question isn't very clear, I presume that the numbers found must all be different. Otherwise, one could make 2 = 1³ + 1³ and every number larger than one could be represented by the sum of a lot of cubed ones (i.e. n = 1³ + 1³ + 1³ + ...).

The algorithm is this:

The first step is to have a for counting i down from cbrt(n) to 1 trying to form cubes.
Then, subtract the cube from n and recursively try to find a cube sum for the resulting number.
Add a parameter to avoid repeating numbers, which is one smaller than the last number used.
When a cube is formed, return the number that formed it. In the outer calls, add the result to the list of non-empty inner recursive call.
If an inner recursive call gives an empty list as a result, then the current iteration of the for produced a bad number and we should try the next one (if we have a next one).
If the for ends without a cube forming, return an empty list.

Here is the code:

import java.util.LinkedList;
import java.util.List;

public class Main {
    public static List findCubeSum(int n) {
        return findCubeSum(n, n);
    }

    public static List findCubeSum(int n, int max) {
        if (n <= 0) return List.of();
        int c = (int) Math.cbrt(n);
        for (int i = Math.min(c, max); i > 0; i--) {
            int x = i * i * i;
            if (x == n) {
                List result = new LinkedList<>();
                result.add(i);
                return result;
            }
            List result = findCubeSum(n - x, i - 1);
            if (result.isEmpty()) continue;
            result.add(0, i);
            return result;
        }
        return List.of();
    }

    public static void main(String[] args) {
        System.out.println(findCubeSum(8));    // [2]
        System.out.println(findCubeSum(64));   // [4]
        System.out.println(findCubeSum(1000)); // [10]
        System.out.println(findCubeSum(1072)); // [10, 4, 2]
        System.out.println(findCubeSum(1944)); // [12, 6]
        System.out.println(findCubeSum(4));    // []
        System.out.println(findCubeSum(0));    // []
        System.out.println(findCubeSum(-1));   // []
        System.out.println(findCubeSum(10));   // []
    }
}

See it running at ideone.

Recursion and While Loops in Java

Answers (2)

Related Questions