Java 8 Lambda expressions for solving fibonacci (non recursive way)

Question

I am a beginner in using Lambda expression feature in Java 8. Lambda expressions are pretty well useful in solving programs like Prime number check, factorial etc.

However can they be utilized effectively in solving problems like Fibonacci where the current value depends on sum of previous two values. I have pretty well solved prime number check problem effectively using Lambda expressions. The code for the same is given below.

boolean checkPrime=n>1 && LongStream.range(2, (long) Math.sqrt(n)).parallel().noneMatch(e->(n)%e==0);

In the above code in the noneMatch method we are evaluating with the current value(e) in the range. But for the Fibonacci problem, we requires previous two values.

How can we make it happen?

Answer 1

The simplest solution is to use a stream of Pairs:

Stream.iterate(new long[] { 1, 1 }, p -> new long[] { p[1], p[0] + p[1] })
      .limit(92)
      .forEach(p -> System.out.println(p[0]));

Due to the lack of a standard pair type, it uses a two-element array. Further, I use .limit(92) as we can't evaluate more elements using long values. But it's easy to adapt to BigInteger:

Stream.iterate(new BigInteger[] { BigInteger.ONE, BigInteger.ONE },
               p -> new BigInteger[] { p[1], p[0].add(p[1]) })
      .forEach(p -> System.out.println(p[0]));

That'll run until you haven't enough memory to represent the next value.

By the way, to get the nth element from the stream:

Stream.iterate(new long[] { 1, 1 }, p -> new long[] { p[1], p[0] + p[1] })
      .limit(91)
      .skip(90)
      .findFirst()
      .get()[1];

Answer 2

To get the Nth fibonacci element (using reduction):

Stream.iterate(new long[] {1, 1}, f -> new long[] { f[1], f[0] + f[1] })
    .limit(n)
    .reduce((a, b) -> b)
    .get()[0];

Here is what is going on:

• Stream::iterate - is producing pairs of numbers, each containing two consecutive elements of fibonacci. We have to use pairs, because we can access only the last element via "iterate", not two or more previous elements, so to generate a new pair, we get the last pair, which already contains two previous elements of fibonacci, and produce the next pair. And to get the Nth fibonacci element, we just need to get the left value from the Nth pair.

• .limit(n) - to keep the first N pairs, and exclude the rest.

• .reduce((a, b) -> b) - to get the last pair from the stream of N pairs from previous step.

• .get()[0] - extract fibonacci element from the pair (left value of the pair)

Answer 3

solving fibonacci (non recursive way)

This is not going to happen with your approach

The generation of Fibonacci numbers based on the previous two numbers is based on the previous two numbers, i.e. it's a recursive algorithm, even if you implement it without recursion but in a loop.

There's other ways based on the matrix exponential so you can calculate the n'th fibonacci number without calculating the n-1 previous numbers, but for your problem (calculating the series), this doesn't make sense.

So, to answer your question in the end, namely how can I use Lambda expressions on the two previous elements?: have a list of tuples, each containing two consecutive numbers, and iterate over that, adding a new tuple every step.