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

Question

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;
    }
}

You need to move the "should I stop now" check inside recursion. As it stands, both branches of the if call the function again, and it loops forever. — Matthew Strawbridge
– Matthew Strawbridge, Commented May 30, 2016 at 20:57
in which situation do you think you can exit the recursion method? — njzk2
– njzk2, Commented May 30, 2016 at 21:48

Alex Hall · Accepted Answer · 2016-05-30 21:12:44Z

3

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

edited May 30, 2016 at 21:12

answered May 30, 2016 at 20:59

Alex Hall

36.2k5 gold badges63 silver badges98 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

shoes Over a year ago

Thanks for the tips. Unfortunately that was the way I had it originally and moved it out in hopes to resolve. Forgot to move it back before posting. When I place it inside it still loops. public static void recursion(long n) { if (n != 1) { if (n % 2 == 0) { recursion(n/2); } else { recursion(n*3-1); } System.out.println ("number: " + n); } return; }

Alex Hall Over a year ago

Make sure that you check the base case first, and if it's true, that the function returns before it can get to the recursive calls. Also move the print so you can see what's happening. If you still can't get it then edit your question with the latest code.

shoes Over a year ago

Changed base case to check for true but it still loops. Also added the print statements in each "if" statement but never get one to print. changed code: public static void recursion(long n) { if (n == 1) return; { if (n % 2 == 0) { recursion(n/2); System.out.println ("even number: " + n); } else { recursion(n*3-1); System.out.println ("odd number: " + n); } }

Alex Hall Over a year ago

@shoes You need to print before the recursion to see what's happening. I can't see anything wrong with your code. Check my updated answer.

Alex Hall Over a year ago

@shoes I tested both bits of code that you commented here and they worked fine. You're doing something wrong somewhere else.

|

Collectives™ on Stack Overflow

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

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related