是否有可能在 Java 8 中创建一个通过递归定义的、以惰性方式无限增长的集合？

我可以创建一个递归闭包：

static IntUnaryOperator fibo;
fibo = 
    (i) -> 
    i<2 ? 1 : fibo.applyAsInt(i-1)+ fibo.applyAsInt(i-2);

但当然，它仅作为示例才有意义。为了有用，这样的集合应该保留已经计数过的元素并 get() 它们而不重新计数。元素的计数应该在第一次需要时以惰性方式进行。因此，任何成员都不必计算多次。通过这种方式，我们将得到一个看起来像递归定义的序列的结构，并且快速且可重用。

当我开始学习 Java 8 时，我认为 Stream 就是这样工作的。但事实并非如此，因为流不能使用两次。

我考虑了以下构建：

IntStream fi;
fi=IntStream.iterate(0, i -> fi[i-1]+fi[i-2]);

但这样它就行不通——我无法通过索引从流中获取项目。另一个问题是，如果我稍后沿着流走，它将被消耗，并且我不能重复使用它。如果我将流复制到 List，它就不再是懒惰的了。

因此，我需要一些可以通过索引来解决的构造。作为fibo(i).

编辑。显然，该解决方案不能是流，因为流不能被使用两次。我不想在每次调用 F(i) 时重复所有计算。

看来你在要求这样的事情：

public class Fibonacci extends AbstractList<BigInteger> {
    @Override
    public Stream<BigInteger> stream() {
        return Stream.iterate(new BigInteger[]{ BigInteger.ONE, BigInteger.ONE },
           p->new BigInteger[]{ p[1], p[0].add(p[1]) }).map(p -> p[0]);
    }
    @Override
    public Iterator<BigInteger> iterator() {
        return stream().iterator();
    }
    @Override
    public int size() {
        return Integer.MAX_VALUE;
    }
    @Override
    public BigInteger get(int index) {
        return stream().skip(index).findFirst().get();
    }
}

可以通过以下方式访问List接口（它没有实现RandomAccess有充分的理由），因此，您可以通过以下方式询问第 n 个值get(n)。请注意，执行get提示您如何获取之后位置的值Integer.MAX_VALUE。只需使用stream().skip(position).findFirst().get().

谨防！这份清单是infinite，正如你所要求的。不要要求它对所有元素进行操作，例如甚至不toString()。但像下面这样的事情将会顺利进行：

System.out.println(new Fibonacci().subList(100, 120));

or

for(BigInteger value: new Fibonacci()) {
    System.out.println(value);
    if(someCondition()) break;
}   

但是，当您必须处理大型元素序列并希望高效地完成时，您应该确保在迭代器或流上工作，以避免O(n²)重复的复杂性get calls.

请注意，我将元素类型更改为BigInteger因为当涉及到斐波那契数列和int or long值类型。即使与longvalue 类型，仅 92 个值后序列就结束，发生溢出。

更新：既然你明确表示你正在寻找一个懒惰的人storage，您可以按如下方式更改上面的类：

public class Fibonacci extends AbstractList<BigInteger> {
    final Map<BigInteger,BigInteger> values=new HashMap<>();

    public Fibonacci() {
        values.put(BigInteger.ONE, BigInteger.ONE);
        values.put(BigInteger.ZERO, BigInteger.ONE);
    }

    @Override
    public BigInteger get(int index) {
        return get(BigInteger.valueOf(index));
    }
    public BigInteger get(BigInteger index) {
        return values.computeIfAbsent(index, ix ->
            get(ix=ix.subtract(BigInteger.ONE)).add(get(ix.subtract(BigInteger.ONE))));
    }

    @Override
    public Stream<BigInteger> stream() {
        return Stream.iterate(BigInteger.ZERO, i->i.add(BigInteger.ONE)).map(this::get);
    }
    @Override
    public Iterator<BigInteger> iterator() {
        return stream().iterator();
    }
    @Override
    public int size() {
        return Integer.MAX_VALUE;
    }
}

I used BigInteger作为这里的键/索引来满足（理论上）无限的要求，尽管我们可以使用long也是所有实际用途的关键。关键点是最初为空的存储：（现在示例性地使用long):

final Map<Long,BigInteger> values=new HashMap<>();

它是用应该结束每个递归的值预先初始化的（除非由于已经计算的值而提前结束）：

values.put(1L, BigInteger.ONE);
values.put(0L, BigInteger.ONE);

然后，我们可以通过以下方式请求一个延迟计算值：

public BigInteger get(long index) {
    return values.computeIfAbsent(index, ix -> get(ix-1).add(get(ix-2)));
}

或委托给的流get上述方法：

LongStream.range(0, Long.MAX_VALUE).mapToObj(this::get);

这创建了一个“实际上无限”的流，而上面的完整示例类使用BigInteger理论上是无限的……

The Map将记住序列的每个计算值。