shoes shoes - 6 months ago 24
Java Question

Recursion - Exception in thread "main" java.lang.StackOverflowError

I am required to write a recursive method. I have written the code to perform the task without recursion. I am getting the error Exception in thread "main" java.lang.StackOverflowError at Exercise13r.recursion(Exercise13r.java:29). Code is... to enter a number then if result is even, divide by 2, if result is odd, multiply by 3 and subtract 1. Obviously I am looping but not sure why. Any assistance would be appreciated.

import java.util.Scanner;
public class Exercise13r
{
public static void main(String[] args)
{
// Initialize variables
long number = 0;
Scanner in = new Scanner(System.in);
System.out.println ("Enter a starting number: ");
number = in.nextInt ();
System.out.println ("Your starting number is: " + number);
if (number != 1)
{
recursion(number);
}
}

public static void recursion(long n)
{
if (n % 2 == 0)
{
recursion(n/2);
}
else
{
recursion(n*3-1);
}
System.out.println ("number: " + n);
return;
}
}

Answer

Your base case if (number != 1) needs to be inside the definition of the function so that it actually knows when to stop. Right now your program eventually reduces to calling recursion(1) and your function will still call itself recursively (what else can it do?) so it ends up calling recursion(2) which leads to recursion(1) again and so on.

Note that this becomes apparent if you move System.out.println ("number: " + n); before the recursive calls. Since you have infinite recursion it never gets around to printing anything preventing you from seeing the problem.

Here is a minimal working example:

class Exercise13r {
    public static void main(String[] args) {
        recursion(12);
    }

    public static void recursion(long n) {
        System.out.println ("number: " + n);
        if (n != 1) {
            if (n % 2 == 0) {
                recursion(n/2);
            } else {
                recursion(n*3-1);
            }
        }
    }
}

Output:

number: 12
number: 6
number: 3
number: 8
number: 4
number: 2
number: 1