Thinking functionally - Java 8 in Action: Lambdas, Streams, and Functional-Style Programming - page 367

The first listing demonstrates a standard loop-based form: the variables r and i are updated at
each iteration. The second listing shows a recursive definition (the function calls itself) in a more
mathematically familiar form. In Java, recursive forms are typically less efficient, and we discuss
this shortly.
But if you've read the earlier chapters of this topic, then you know that Java 8 streams provide
an even simpler declarative way of defining factorial, as the next listing shows.
Listing 13.3. Stream factorial
static long factorialStreams(long n){
return LongStream.rangeClosed(1, n)
.reduce(1, (long a, long b) -> a * b);
}
Now let's turn to efficiency. As Java users, you should beware of functional-programming
zealots who tell you that you should always use recursion instead of iteration. In general, making
a recursive function call is much more expensive than the single machine-level branch
instruction needed to iterate. Why? Every time the factorialRecursive function is called, a new
stack frame is created on the call stack to hold the state of each function call (the multiplication
it needs to do) until the recursion is done. This means your recursive definition of factorial will
take memory proportional to its input. This is why if you run factorialRecursive with a large
input, you're likely to receive a StackOverflowError:
Exception in thread "main" java.lang.StackOverflowError
Does this mean recursion is useless? Of course not! Functional languages provide an answer to
this problem: tail-call optimization . The basic idea is that you can write a recursive definition of
factorial where the recursive call is the last thing that happens in the function (we say the call is
in a tail position). This different form of recursion style can be optimized to run fast. To
exemplify, here's a tail-recursive definition of factorial
Listing 13.4. Tail-recursive factorial
static long factorialTailRecursive(long n) {
return factorialHelper(1, n);
}
static long factorialHelper(long acc, long n) {
return n == 1 ? acc : factorialHelper(acc * n, n-1);