Generating a stream of Fibonacci numbers

A Java stream represents potentially an infinite sequence of data. This is a simple post that will go into the mechanics involved in generating a simple stream of Fibonacci numbers.

The simplest way to get this stream of data is to use the generate method of Stream.

As you can imagine to generate a specific Fibonacci number in this sequence, the previous two numbers are required, which means the state of the previous two numbers need to be maintained somewhere. The two solutions that I will be describing here both maintain this state, however they do it differently.

Mutable State

In the first approach, I am just going to maintain state this way:

class FibState {

    private long[] prev = new long[2];

    private int index = 0;

 

    public long nextFib() {

        long result = (index == 0) ? 1

                : ((index == 1) ? 1 : prev[0] + prev[1]);

        prev[0] = prev[1];

        prev[1] = result;

        index++;

        return result;

    }

}

with index keeping track of the index of the current fibonacci number in the sequence and prev capturing the most recent two in the sequence. So the next in the series is generated by mutating the index and the changing the array holding the recent values. So given this state, how do we generate the stream, using code which looks like this:

Stream<Long> streamOfFib() {

    FibState fibState = new FibState();

    return Stream.generate(() -> fibState.nextFib());

}

This is using a closure to capture the fibState and mutating it repeatedly as the stream of numbers is generated. The approach works well, though the thought of mutating one value probably should induce a level of dread – is it thread safe (probably not), will it work for parallel streams(likely not), but should suffice for cases where the access is strictly sequential. A far better approach is to get a version of state that is immutable.

Immutable State

class FibState {

    private final long[] prev;

    private final int index;

 

    public FibState() {

        this(new long[]{-1, 1}, 0);

    }

 

    public FibState(long[] prev, int index) {

        this.prev = prev;

        this.index = index;

    }

 

    public FibState nextFib() {

        int nextIndex = index + 1;

        long result = (nextIndex == 1) ? 1 : prev[0] + prev[1];

        return new FibState(new long[]{prev[1], result}, nextIndex);

    }

 

    public long getValue() {

        return prev[1];

    }

}

Instead of mutating the state, it returns the next immutable state. Alright, so now that this version of state is available, how can it be used – by using the “iterate” function of Stream, like this:

Stream<Long> streamOfFib() {

    return Stream

            .iterate(new FibState(), fibState -> fibState.nextFib())

            .map(fibState -> fibState.getValue());

}

this function takes two parameters – the initial state and something which can generate the next state. Also to return numbers from it, I am mapping this “state” type to a number in the “map” operation.