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

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

当然，它仅作为示例有意义。为了有用，这样的集合应该保留已经计算过一次的元素，并在不重新计算的情况下获取()它们。元素的计数应该以懒惰的方式发生，首先需要。因此，任何成员都必须计算一次以上。通过这种方式，我们将得到一个看起来像递归定义的序列的结构，并且速度快且可重用。

当我开始学习 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 接口(interface)访问(它没有实现 RandomAccess 是有充分理由的)，因此，您可以通过 请求第 n 个值>得到(n)。请注意，get 的实现提示您如何获取 Integer.MAX_VALUE 之后位置的值。只需使用 stream().skip(position).findFirst().get()。

当心!正如您所要求的，这个列表无限。不要要求它对所有元素进行操作，例如甚至 toString()。但是像下面这样的事情会顺利进行:

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

或

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

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

请注意，我将元素类型更改为 BigInteger，因为在涉及 Fibonacci 序列和 int 或 时考虑无限流是没有意义的长 值类型。即使使用 long 值类型，序列也只在 92 个值之后结束，因为那时会发生溢出。

更新:既然您明确表示您正在寻找惰性存储，您可以按如下方式更改上面的类:

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;
    }
}

我在这里使用 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)));
}

或委托(delegate)给上述get方法的流:

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

这将创建一个仅“几乎无限”的流，而上面使用 BigInteger 的完整示例类在理论上是无限的……

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

关于java - 是否有可能在 Java 8 中创建一个无限增长的惰性集合，由递归定义？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33826306/