Stackoverflow error in this recursion

Question

What's wrong with this recursion in Java?

public class findPyt
{
    public static int sum = 0;
    public static void main(String[] args)
    {
        findP(3, 4, 5);
    }

    public static void findP(int a, int b, int c)
    {
        sum = a+b+c;

        if (sum == 1000)
        {
            System.out.println("The Triplets are: "+ a +","+ b +","+ c);
        }
        else
        {
            findP(a*2, b*2, c*2);
        }
    }
}

I get this exception:

Exception in thread "main" java.lang.StackOverflowError
    at hello.findP(hello.java:12)
    at hello.findP(hello.java:19)

When I try to do the same in Ruby, I get this:

SystemStackError: stack level too deep


def pythagoreanTriples(a=3, b=4, c=5)

    if (a+b+c) == 1000
      puts "The Triplets are: "+ a +","+ b +","+ c
    else
    pythagoreanTriples(a*2, b*2, c*2)
    end
end

Answer 1

Try changing sum == 1000 to sum >= 1000. There is no triple that sums to exactly 1000, so it's skipping over the terminating condition.

Also, your Ruby code doesn't match your Java code (you're missing else). Even if it did find a sum of 1000, it would print the message, and keep recursing until it crashed.

Answer 2

Well, you construct infinite recursion here, without anything to stop it. Sure it breaks with an error of stack being full.

Answer 3

Well, if you look at your method that performs the recursion, the only exit condition is when sum == 1000. Your current input values are 3, 4, and 5. That sum is 12. The condition doesn't hold true, so it tries the next set, where sum = 24. Then 48, 96 and so forth. The sum will never be 1000, so the recursion will never end.

Answer 4

3+4+5 is 12.

a*2 + b*2 + c*2 = (a+b+c)*2

12*2*2 = 12*4

Now, let's see: Your program will stop when the sum equals 1000. That will never happen, the sequence will be:

12 24 48 96 192 384 768 1536 ...

Unless some sort of integer overflow rescues you, you will never reach 1000. And, since you are using recursion, eventually a stack overflow happens(if you managed to solve the problem without recursion, it'd be an infinite loop)

Answer 5

By the way, you are multiplying by two. You need to raise to the power two, so a^2 or a**2.

I'm basing this on the word "pythagoreanTriples" in the code.

Answer 6

Beyond the bug in your code which other answers have described, using recursion in Java in this way is problematic anyway. You are using tail recursion, so the compiler or the JVM could convert the call to a jump to the beginning of the procedure and consume no stack space; however, this is not done (to preserve accurate stack traces).

E.g., processing a list in such a way in Java would cause your code to be limited to processing only lists of limited length before a stack overflow, and even when it works you would get slower performance and higher memory consumption. But the possibility of a crash (for say more than 1-10 million elements, since the stack is by default 8MiB) is more important.

If you were to program in Scala you, or other functional languages, that style would be appropriate and efficiently supported.