How come I got this error by using recursion?

Question

If I enter 33333 I get this error. I check many times, but I don't know how to wrok it out. If I enter the number that is greater than 33333, and it works fine. What's wrong with 33333?

My log:

Exception in thread "AWT-EventQueue-0" java.lang.StackOverflowError
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)
at piande.PiandE.factorial(PiandE.java:67)

My code:

private double factorial(long number) {
    if (number <= 1) {         // if number is smaller of eaqual to 1 then return directly
        return 1; //factorial of 1 is 1
    } else {
        return number * factorial(number - 1); //using recursion to reuse the method until number be 1
    }
}

As a side note for the factorial, consider using the [Gamma Function](https://en.wikipedia.org/wiki/Gamma_function). [Apache](http://commons.apache.org/proper/commons-math/javadocs/api-3.3/org/apache/commons/math3/special/Gamma.html) provides and implementation. — bradimus, Nov 07 '16 at 18:47
You can't recurse that deeply. I'm not sure why you think that a larger input makes the stack overflow go away. Your code overflows for me on any input of 5025 or higher. — azurefrog, Nov 07 '16 at 18:54
Your program simply runs out of call stack. Check this post to know about dept of call stack http://stackoverflow.com/questions/4734108/what-is-the-maximum-depth-of-the-java-call-stack — Arthas, Nov 07 '16 at 18:58
How it happens to be that the factorial method is taking longs but returning doubles??? — ΦXocę 웃 Пepeúpa ツ, Nov 07 '16 at 19:02

score 2 · Answer 1 · answered Nov 07 '16 at 18:48

2

Recursion is an extremely innefficient way of calculating a factorial, it is also unfortunately used in almost every intro to recursion in programming courses. Try an iterative approach instead!

answered Nov 07 '16 at 18:48

chatton

596
1
3
8

1

I don't think that that's unfortunate - it's a good recursive function for learning. A lot of homework assignments are, by their very nature, somewhat artificial or have unusual constraints; they're not *supposed* to be exactly the same as the way you'd solve the problem in the "real world." – EJoshuaS - Stand with Ukraine Nov 07 '16 at 19:02
1

Yes that's true, I understand why they introduce the topic of recursion with things like factorial and Fibonacci sequence algorithms, but I feel like there are also plenty of other good examples for when recursive algorithms could be used and are a decent solution. Things like a simple BFS or DFS, several recursive sorting algorithms (granted theses may be a bit much if you're first learning about recursion) – chatton Nov 07 '16 at 19:32

EJoshuaS - Stand with Ukraine · Accepted Answer · 2016-11-08T17:16:27.870

When I tested it (granted, in C# rather than Java, but the syntax is identical and it behaves in a similar way) I get a similar error for all similar values - not just that particular number.

Keep in mind that every time you do a recursive call you're growing the stack, so it's usually the case that if you have too many recursive calls you'll eventually run out of space simply by virtue of the fact that the stack becomes too large.

Memoization (which entails storing intermediate results so that the program doesn't have to take as many steps; for example, if you know 10,000!, you can save thousands of calculations on larger values) can improve the situation, as can using tail recursion (in languages that support it) or, equivalently, a "for" loop (which doesn't grow the stack at all).

Keep in mind, too, that eventually the factorial will become larger than even the long or double types can represent, so the stack overflow exception won't be your only problem for representing them.

gimbup · Answer 3 · 2016-11-07T18:49:03.027

0

Don't use recursion, use loop. Every time you call a method, the stack will grow, and it will eventually get full, that's why it says stack overflow.

So don't use recursion when you think it will call the same method a lot of times

edited Nov 07 '16 at 18:49

answered Nov 07 '16 at 18:44

gimbup

184
3
18

I know using loop is more efficiency, but why did get this error? – Jinyu Wu Nov 07 '16 at 18:46

score 0 · Answer 4 · answered Nov 07 '16 at 21:52

Your code is exceeding the stack limit, but you could "unroll" part of the recursion. If you also use BigInteger you can calculate your very large result. Something like,

private static BigInteger factorial(long number) {
    if (number <= 1) {
        return BigInteger.ONE;
    } else if (number > 7) {
        return BigInteger.valueOf(number)//
                .multiply(BigInteger.valueOf(number - 1))//
                .multiply(BigInteger.valueOf(number - 2))//
                .multiply(BigInteger.valueOf(number - 3))//
                .multiply(BigInteger.valueOf(number - 4))//
                .multiply(BigInteger.valueOf(number - 5))//
                .multiply(BigInteger.valueOf(number - 6))//
                .multiply(factorial(number - 7));
    } else {
        return BigInteger.valueOf(number).multiply(factorial(number - 1));
    }
}

Which I ran with

public static void main(String args[]) {
    System.out.println(factorial(33333));
}

The result is, as mentioned, a little large to post.

How come I got this error by using recursion?

4 Answers4