How to fix a stack overflow in my java program?

Question

So, I am studying java, and as a first exercise I decided to write two small and composable functions, namely a fibbonacci and a factorial function, which have a common implementation detail, however I received a stack overflow exception when I tried to separate their common part into a separate function. Any tips on what am I doing wrong?

public class BaseFunctions{

    static Integer factorial(Integer num) {

        return factorial(comComponent(num)-1)*num;

    }

    static Integer fibbonacci(Integer num) {

     return fibbonacci(comComponent(num)-1) + fibbonacci(comComponent(num)-2);
    }       

    static Integer comComponent(Integer num) {

        if(num == 1 || num == 0) {
            return 1;

        }else if(num < 0){

            throw new ArithmeticException("Num must be > 0");

        }else return num;

    }
}

It seems you basically never get of out of the "fibonacci" method. — LppEdd
– LppEdd, Commented Mar 31, 2019 at 13:06
See introcs.cs.princeton.edu/java/23recursion/Fibonacci.java.html for an example. — LppEdd
– LppEdd, Commented Mar 31, 2019 at 13:11

StrahR · Accepted Answer · 2019-03-31 13:10:38Z

2

When you reach num = 0, comComponent will return 1, calling your function with num = 0 again, thus getting stuck in an infinite loop.

answered Mar 31, 2019 at 13:10

StrahR

213 bronze badges

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

Comments

forpas · Accepted Answer · 2019-03-31 13:58:02Z

A recursive function must have an exit point (which must be checked first before any recursive call), if not this leads to Stack Overflow.
What you do is leave the function without that exit point, be delegating (or so you think) this functionality to comComponent().
But take a look at the code inside factorial():

return factorial(comComponent(num)-1)*num;

Why should it ever stop? There is no return statement without a recursive call.
So your logic is wrong.
Drop comComponent() and stick to the traditional way:

static Integer factorial(Integer num) {
    if (num == 1 || num == 0)
        return 1;
    else if (num < 0)
        throw new ArithmeticException("Num must be > 0");
    else
        return factorial(num - 1) * num;
}

static Integer fibbonacci(Integer num) {
    if (num == 1 || num == 0)
        return 1;
    else if (num < 0)
        throw new ArithmeticException("Num must be > 0");
    else
        return fibbonacci(num - 1) + fibbonacci(num - 2);
}

As you can see both functions have an exit point:

if (num == 1 || num == 0)
    return 1;

Collectives™ on Stack Overflow

How to fix a stack overflow in my java program?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related