java - 用 Stream 替换 for 循环中的递归

Question

我无法用 Stream 替换包含递归调用的 for 循环。该代码是关于在已知该数字的质因数时生成给定数字的适当除数。算法取自here , 它在图像中被描述。这是我用于演示目的的代码的一部分，它是可运行的:

public class Demo {

    private static void generateDivisorsTraditional(int start, long lastFactor, Multiset<Long> primeFactors, Set<Long> divisors) {
        for (int i = start; i < primeFactors.elementSet().size(); i++) {
            long prime = Iterables.get(primeFactors.elementSet(), i);
            int count = primeFactors.count(prime);
            ++start;

            for (int c = 0; c <= count; c++) {
                long factor = ArithmeticUtils.pow(prime, c);
                divisors.add(lastFactor * factor);
                generateDivisorsTraditional(start, lastFactor * factor, primeFactors, divisors);
            }
        }
    }

    private static void generateDivisorsStream(int start, long lastFactor, Multiset<Long> primeFactors, Set<Long> divisors) {
        IntStream.range(start, primeFactors.elementSet().size())
                .forEach((int i) -> {
                    long prime = Iterables.get(primeFactors.elementSet(), i);
                    int count = primeFactors.count(prime);
                    final int begin = start + 1;

                    IntStream.range(0, count + 1)
                            .forEach((int c) -> {
                                long factor = ArithmeticUtils.pow(prime, c);
                                divisors.add(lastFactor * factor);
                                generateDivisorsStream(begin, lastFactor * factor, primeFactors, divisors);
                            });
                });
    }

    private static void testTraditional(Multiset<Long> primeFactors) {
        Set<Long> divisors = new TreeSet<>();
        generateDivisorsTraditional(0, 1, primeFactors, divisors);
        System.out.println("Traditional=> " + divisors);
    }

    private static void testStream(Multiset<Long> primeFactors) {
        Set<Long> divisors = new TreeSet<>();
        generateDivisorsStream(0, 1, primeFactors, divisors);
        System.out.println("Stream=> " + divisors);
    }

    private static void testStream1(Multiset<Long> primeFactors) {
        Set<Long> divisors = new TreeSet<>();
        new Inner().generateDivisorsStream(1, primeFactors, divisors);
        System.out.println("Stream1=> " + divisors);
    }

    public static void main(String[] args) {
        System.out.println("Test number: 10");
        Multiset<Long> primeFactors = TreeMultiset.create();
        primeFactors.add(2L);
        primeFactors.add(5L);

        testTraditional(primeFactors);
        testStream(primeFactors);
        testStream1(primeFactors);

        System.out.println();

        System.out.println("Test number: 90");
        primeFactors = TreeMultiset.create();
        primeFactors.add(2L);
        primeFactors.add(3L);
        primeFactors.add(3L);
        primeFactors.add(5L);

        testTraditional(primeFactors);
        testStream(primeFactors);
        testStream1(primeFactors);
    }

    private static class Inner {
        private int start = 0;

        private void generateDivisorsStream(long lastFactor, Multiset<Long> primeFactors, Set<Long> divisors) {
            IntStream.range(start, primeFactors.elementSet().size())
                    .forEach((int i) -> {
                        long prime = Iterables.get(primeFactors.elementSet(), i);
                        int count = primeFactors.count(prime);
                        ++start;

                        IntStream.range(0, count + 1)
                                .forEach((int c) -> {
                                    long factor = ArithmeticUtils.pow(prime, c);
                                    divisors.add(lastFactor * factor);
                                    generateDivisorsStream(lastFactor * factor, primeFactors, divisors);
                                });
                    });
        }
    }
}

它生成的输出是:

Test number: 10
Traditional=> [1, 2, 5, 10]
Stream=> [1, 2, 5, 10, 25]
Stream1=> [1, 2, 5]

Test number: 90
Traditional=> [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90]
Stream=> [1, 2, 3, 5, 6, 9, 10, 15, 18, 25, 27, 30, 45, 50, 75, 81, 90, 125, 135, 225, 405]
Stream1=> [1, 2, 3, 5, 9]

顾名思义，generateDivisorsTraditional 方法使用传统的 for 循环，在其中我递归调用了相同的方法。 generateDivisorsStream 方法使用 IntStream.range() 来模拟 for 循环。

我怀疑 ++start; 和 final int begin = start + 1; 的 generateDivisorsTraditional 和 generateDivisorsStream 分别做了一些不同。我也尝试在 generateDivisorsTraditional 中使用 final int begin = start + 1; 而不是 ++start; 并发现它已经开始产生错误的结果。我在内部类 Inner 中还有另一个变体，它也会产生错误的输出。

我想知道为什么这不是它应该的行为方式？我犯了什么错误？

Answer 1

我认为有一些错误:

private static void generateDivisorsTraditional(int start, long lastFactor, Multiset<Long> primeFactors, Set<Long> divisors) {
    for (int i = start; i < primeFactors.elementSet().size(); i++) {
        long prime = Iterables.get(primeFactors.elementSet(), i);
        int count = primeFactors.count(prime);
        // ++start; remove it

        for (int c = 0; c <= count; c++) {
            long factor = ArithmeticUtils.pow(prime, c);
            divisors.add(lastFactor * factor);
            generateDivisorsTraditional(i+1, lastFactor * factor, primeFactors, divisors); // replaced start -> i+1
        }
    }
}

private static void generateDivisorsStream(int start, long lastFactor, Multiset<Long> primeFactors, Set<Long> divisors) {
    IntStream.range(start, primeFactors.elementSet().size())
            .forEach((int i) -> {
                long prime = Iterables.get(primeFactors.elementSet(), i);
                int count = primeFactors.count(prime);
                IntStream.range(0, count + 1)
                        .forEach((int c) -> {
                            long factor = ArithmeticUtils.pow(prime, c);
                            divisors.add(lastFactor * factor);
                            generateDivisorsStream(i+1, lastFactor * factor, primeFactors, divisors);
                        });
            });
}

public static void main(String[] args) {
    Multiset<Long> m = HashMultiset.create();
    m.add(1L, 1);
    m.add(2L, 1);
    m.add(5L, 1);
    Set<Long> divisors = new HashSet<>();
    generateDivisorsTraditional(1, 1, m, divisors);
    System.out.println("Traditional=> "+divisors);
    divisors = new HashSet<>();
    generateDivisorsStream(1, 1, m, divisors);
    System.out.println("Stream=> "+divisors);
}

它打印:

Traditional=> [1, 2, 5, 10]
Stream=> [1, 2, 5, 10]