calculate factorial recursive in functional style Java

Question

I try to calculate factorial in a functional style.

I did this:

 private static Function<BigInteger, BigInteger> factorial = x -> BigInteger.ONE.equals(x)
        ? BigInteger.ONE
        : x.multiply(Main.factorial.apply(x.subtract(BigInteger.ONE)));

And I have got StackOverflowError when trying to get 11111!

BUT when I calculate factorial using this method:

private static BigInteger factorial(BigInteger request) {
    if (BigInteger.ONE.equals(request)) return BigInteger.ONE;
    else return request.multiply(factorial(request.subtract(BigInteger.ONE)));
}

I can get the result without StackOverflowError.

Is functional style less effective? Why?

I am confused. What does this have to do with "Sum of all elements in array"? — Jörg W Mittag, Dec 31 '19 at 14:10
This has nothing to do with functional style perse (btw: both are equally functional style), the main difference - as a guess - could be that lambda's might incur additional overhead that could increase the stack size per call, so you'll run out of stack space quicker. — Mark Rotteveel, Dec 31 '19 at 15:06
@JörgWMittag sorry for the misunderstanding) I forgot to change the name of the question, at first I wanted to take an example from a book about algorithms, but then replaced it with factorial calculation — Vadim Chemodurov, Dec 31 '19 at 18:36
Maybe it creates a new instace of the functional interface any time and it is allocated on the stack for optimization... — dan1st, Dec 31 '19 at 18:48
Java has no optimization for tail-recursion, so there is always a limit. Related: https://stackoverflow.com/questions/53354898/tail-call-optimisation-in-java — tevemadar, Dec 31 '19 at 20:06

Anush Shrestha · Accepted Answer · 2019-12-31T19:58:47.673

2

There are twice as many calls in the functional style as compared to function calls. see image.

So while the stack size increases to 11,111 calls in latter, it increases by over 22,222 calls in functional style. I believe stack limit in your environment should be between 11111 and 22222 so that explains why it breaks. So in this sense Functional style seems inefficient.

You can increase the stack size using -Xss described in the below link.

Or, better to use tail recursion which looks something like this:

private static BiFunction<BigInteger, BigInteger, BigInteger> factorialTR = (n, acc) -> BigInteger.ONE.equals(x)
    ? BigInteger.ONE
    : Main.factorialTR.apply(x.subtract(BigInteger.ONE), acc * n));

This will still cause StackoverflowError in Java as it does not support tail call optimization. But Scala, lisp do, there you wont get one.

Refs

edited Dec 31 '19 at 19:58

answered Dec 31 '19 at 19:19

Anush Shrestha

318
1
8

I think the question is asking why the lambda fails while a function does not, not *just* why a StackOverflowError happens. – 17slim Dec 31 '19 at 19:25
@17slim Thanks. I have corrected my answer. – Anush Shrestha Dec 31 '19 at 19:59
Interestingly, in my tests, both versions failed around 13000-150000, and a different number for every test. – Jörg W Mittag Jan 01 '20 at 00:51

Jörg W Mittag · Answer 2 · 2019-12-31T19:55:42.630

Your terminology is somewhat confusing. Both of the examples you showed are written in a functional style: there are no side-effects, no mutable state, no loops. Both examples are referentially transparent.

Also, you seem to be under the impression that only one of those examples will throw a StackOverflowError. That is not the case. Both of those will eventually blow the stack.

In fact, in my testing, both of those blew the stack pretty much at the same value.

For the lambda version, I ran multiple tests, and the stack overflow happened at slightly different values each time, the smallest and biggest ones were around 11000 and around 15300.

For the method version, the stack overflow happened pretty consistently between 13901 and 13907.

Initially, I thought that the lambda version would consistently overflow earlier than the method version, because it uses much more complex runtime machinery (LambdaMetaFactory, method handles, call sites, invokedynamic) which increases the stack size. But, it looks like more than increase the stack size, it increases the variance due to its bigger reliance on runtime optimizations and heuristics.

By the way, your code (both versions) has the same two bugs (which are actually the same bug): it doesn't handle factorial of zero (which is one) and it runs into an infinite recursion for negative numbers. A more correct version would be something like:

private static Function<BigInteger, BigInteger> factorial = 
    x ->
        x.compareTo(BigInteger.ZERO) < 0
        ? throw new ArgumentError()
        : BigInteger.ZERO.equals(x)
          ? BigInteger.ONE
          : x.multiply(App.factorial.apply(x.subtract(BigInteger.ONE)));

private static BigInteger factorial(BigInteger request) {
    if (request.compareTo(BigInteger.ZERO) < 0) throw new ArgumentError;
    if (BigInteger.ZERO.equals(request)) return BigInteger.ONE;
    else return request.multiply(factorial(request.subtract(BigInteger.ONE)));
}

calculate factorial recursive in functional style Java

2 Answers2