Tried Euler's #14 again with recursion, didn't work for me. SPOILERS EULER 14th

Question

I posted earlier trying to bruteforce it, but it didn't work. Here's my attempt #2 with recursion (first time using recursive methods). Please help!

Here's what happens: The code runs fine, with smaller numbers, but when we get up to one million, the code simply will run, and nothint at all happens. In Eclipse, it still gives me the option to end, but I've let it run for a very long time with nothing helping.

/**
* The following iterative sequence is defined for the set of positive
* integers:
*
* n → n/2 (n is even) n → 3n + 1 (n is odd)
*
* Using the rule above and starting with 13, we generate the following
* sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
*
* It can be seen that this sequence (starting at 13 and finishing at 1)
* contains 10 terms. Although it has not been proved yet (Collatz Problem),
* it is thought that all starting numbers finish at 1.
*
* Which starting number, under one million, produces the longest chain?
*
* NOTE: Once the chain starts the terms are allowed to go above one
* million.
*/
public class Euler14 {
    static int desiredMax = 1000000;
    static int maxTerm = 0;
    static int maxNumberOfTerms = 0;
    static int currentNumber = 0;
    static int numberOfTerms = 0;
    public static void doMath(int startingNumber) {
        if(startingNumber == 1) {
            System.out.print( maxTerm + " " + maxNumberOfTerms);
        }
        else {
            currentNumber = desiredMax;
            while(currentNumber!= 1) {
                if(currentNumber%2 == 0) {
                    currentNumber = currentNumber/2;
                    numberOfTerms++;
                } else {
                    currentNumber = (3 * currentNumber) + 1;
                    numberOfTerms++;
                }
            }
            numberOfTerms++;
            if(numberOfTerms > maxNumberOfTerms) {
                maxNumberOfTerms = numberOfTerms;
                maxTerm = startingNumber;
            }
            desiredMax--;
            doMath(desiredMax);

        }
    }
    public static void main(String[] args) {

        doMath(desiredMax);
    }

}

Answer 1

There are many wrong things with your code :

• use of a recursive method which is no more no less than a loop going downward
• use of static variables
• numberOfTerms never reinitialized
• as pointed by azurefrog, you have an integer overflow which is causing an infinite loop.

I was rearranging your code with as few changes as possible when he came up with the answer, so all I can do now is to show you a working code very similar to yours. See how cleaner it is this way :

public class Euler14 {
    public static void main(String[] args) {
        int maxTerm = 1000000;
        int maxNumberOfTerms = 1;

        // this loop replaces your recursion, which is not needed here and quite costly even if it is tail-recursion
        for (int i = maxTerm ; i >= 2; i--) {
            int numberOfTerms = 0;
            // declare as long to prevent the overflow
            long currentNumber = i;
            while (currentNumber != 1) {
                if (currentNumber % 2 == 0)
                    currentNumber = currentNumber / 2;
                else
                    currentNumber = (3 * currentNumber) + 1;

                numberOfTerms++;
                if (numberOfTerms > maxNumberOfTerms) {
                    maxNumberOfTerms = numberOfTerms;
                    maxTerm = i;
                }
            }
        }
        System.out.println(maxTerm);
    }
}

Answer 2

The main problem is that you are trying to do math on large numbers with ints. When your program gets down to a desiredMax of 999167, you're going into an infinite loop.

In Java, the largest value an int can represent is 2,147,483,647. When your algorithm gets to 999167, it quickly exceeds that limit. If you print the value of currentNumber in your inner while-loop, you see this:

...
1330496806
665248403
1995745210
997872605
-1301349480    <-- oops
-650674740
-325337370
...

You are trying to set currentNumber to 2,993,617,816, so your value is going to overflow.

This causes your while-loop to never terminate, since you don't account for negative numbers. You quickly settle into a repeating sequence of

-25
-74
-37
-110
-55
-164
-82
-41
-122
-61
-182
-91
-272
-136
-68
-34
-17
-50
-25
... ad infinitum

You could try switching to a bigger numerical representation (long), but, even if you switch to using long values, the way you are trying to recurse will cause a stack overflow long before you ever finish trying to evaluate a desiredMax of 1000000. (On my box, I get a StackOverflowError when I get down to 997474).

You need to go back and rethink the structure of your program. Recursion can be a useful tool, but it's dangerous to use unless you know that you aren't going to go too deep.

Answer 3

This is a good example of where you can employ Memoization.

Below is a solution that uses recursion, but avoids the need to continually go over paths you've calculated already.

This also separates the chain-calculation code from the searching-for-the-maximum code.

public class Euler14 {
    static long[]   records = new long[1000000];

    // //////////////////////////////////////////////
    // Recursively calculates one chain length
    //
    static long getLength(long n) {
        // Terminating condition
        if (n == 1) {
            return n;
        }
        // Have we already calculated this?
        if ((n < records.length) && (records[(int) n] != 0)) {
            return records[(int) n];
        }
        // Haven't calculated this yet, so calculate it now
        long length = getLength(n % 2 == 0 ? n / 2 : 3 * n + 1) + 1;
        // Record the result for later use
        if (n < records.length) {
            records[(int) n] = length;
        }
        return length;
    }

    static long calculateQuestionFourteen() {
        long maxLength = 0;
        long maxStart = 0;
        for (long i = 1; i < 1000000; ++i) {
            long thisLength = getLength(i);
            if (thisLength > maxLength) {
                maxLength = thisLength;
                maxStart = i;
            }
        }
        return maxStart;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(calculateQuestionFourteen());
        System.out.println(System.currentTimeMillis() - start);
    }
}