Generate the Fibonacci sequence using Stream.iterate

• Stream.iterate(seed, f) starts at seed and repeatedly applies the unary operator for the next element.
• Pair encoding: Fibonacci needs two predecessors but iterate passes only one element, so carry {a, b} in a long[].
• Advance function: {a, b} becomes {b, a + b}, sliding the window forward.
• map(f -> f[0]) extracts the first element of each pair, giving the Fibonacci sequence.
• limit(20) bounds the infinite stream.
• Overflow: long overflows around the 93rd term; use BigInteger for more.

What is the challenge with Fibonacci and Stream.iterate?

Stream.iterate passes only the single previous element to the unary operator. But Fibonacci requires the sum of the previous two values. The trick is to encode both predecessors in the carried element by using a two-element array long[]{a, b} as the state.

How do you implement it?

package com.bank.core;

import java.util.List;
import java.util.stream.Stream;

public class FibonacciStream {

    public static void main(String[] args) {
        List<Long> fibonacci = Stream
            .iterate(
                new long[]{0, 1},           // seed: first two values
                f -> new long[]{f[1], f[0] + f[1]})  // advance: slide window
            .map(f -> f[0])                 // extract first of pair
            .limit(20)                      // bound to 20 terms
            .toList();

        System.out.println("Fibonacci (first 20): " + fibonacci);
    }
}

Fibonacci (first 20): [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

How does the state encoding work step by step?

| Step | State {a, b} | Output (a) | Next state {b, a+b} |
|---|---|---|---|
| 0 | {0, 1} | 0 | {1, 1} |
| 1 | {1, 1} | 1 | {1, 2} |
| 2 | {1, 2} | 1 | {2, 3} |
| 3 | {2, 3} | 2 | {3, 5} |
| 4 | {3, 5} | 3 | {5, 8} |

How do you handle overflow for large Fibonacci numbers?

long overflows around the 93rd Fibonacci number (Fib(92) = 7,540,113,804,746,346,429). For larger ranges, use BigInteger.

import java.math.BigInteger;
import java.util.stream.Stream;

List<BigInteger> largeFib = Stream
    .iterate(
        new BigInteger[]{BigInteger.ZERO, BigInteger.ONE},
        f -> new BigInteger[]{f[1], f[0].add(f[1])})
    .map(f -> f[0])
    .limit(100)   // no overflow even at 100th term
    .toList();

How is this different from using Stream.generate?

| Aspect | iterate (Fibonacci) | generate (random) |
|---|---|---|
| Value dependency | Each from previous | Independent |
| State carried | Pair {a, b} | None |
| Ordering | Ordered sequence | Unordered |
| Use case | Recurrences, sequences | Random values, constants |

What are common mistakes?

Mistake: Forgetting to map from the pair to the actual value.

// WRONG: returns long[] pairs, not Fibonacci numbers
Stream.iterate(new long[]{0, 1}, f -> new long[]{f[1], f[0] + f[1]})
    .limit(20)
    .forEach(System.out::println);  // prints array references like [J@...]

// CORRECT: map to f[0] to extract the Fibonacci value
Stream.iterate(new long[]{0, 1}, f -> new long[]{f[1], f[0] + f[1]})
    .map(f -> f[0])
    .limit(20)
    .forEach(System.out::println);

What about using a record instead of an array?

A record makes the state more readable than a raw array.

record FibPair(long a, long b) {
    FibPair next() { return new FibPair(b, a + b); }
}

List<Long> fib = Stream.iterate(new FibPair(0, 1), FibPair::next)
    .map(FibPair::a)
    .limit(20)
    .toList();

What about the three-argument iterate (Java 9)?

The three-argument form can terminate on a condition instead of using limit.

// Fibonacci numbers less than 10,000
List<Long> fibUnder10K = Stream
    .iterate(new long[]{0, 1}, f -> f[0] < 10_000, f -> new long[]{f[1], f[0] + f[1]})
    .map(f -> f[0])
    .toList();

What are common interview follow-up questions?

• "Why do you carry a pair?" Because iterate passes only the last element, but Fibonacci needs two predecessors.
• "When does long overflow?" Around the 93rd Fibonacci number.
• "Can you use BigInteger?" Yes, for arbitrarily large Fibonacci numbers.
• "Can you use a record instead of an array?" Yes, and it is more readable.