Tapas Bose - 1 year ago 85
Java Question

# Replacing recursion within for loop with Stream

I am having trouble to replace a for loop which contains recursive call with

`Stream`
. The code is about generating proper divisors of a given number when the prime factors of that number is known. The algorithm is taken from here, where it is depicted in an image. This is a part my code for demonstration purpose and it is runnable:

``````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);
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);
generateDivisorsStream(begin, lastFactor * factor, primeFactors, divisors);
});
});
}

private static void testTraditional(Multiset<Long> primeFactors) {
Set<Long> divisors = new TreeSet<>();
}

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

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

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

testStream(primeFactors);
testStream1(primeFactors);

System.out.println();

System.out.println("Test number: 90");
primeFactors = TreeMultiset.create();

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

The output it is generating is:

``````Test number: 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]
``````

As the name suggests the method
`generateDivisorsTraditional`
uses traditional for loop and within which I have a recursive call to the same method. The method
`generateDivisorsStream`
uses
`IntStream.range()`
to mimic the for loop.

I am suspecting the instructions
`++start;`
and
`final int begin = start + 1;`
of
`generateDivisorsTraditional`
and
`generateDivisorsStream`
respectively are making some differences. I also have tried to use
`final int begin = start + 1;`
`++start;`
in
`generateDivisorsTraditional`
and have found that it has started generating wrong result. I have also another variant in the inner class
`Inner`
which is also producing wrong output.

I am wondering why this is not behaving the way it is suppose to behave? What is the mistake I have made?

I think there are some mistakes:

``````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);
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);
generateDivisorsStream(i+1, lastFactor * factor, primeFactors, divisors);
});
});
}

public static void main(String[] args) {
Multiset<Long> m = HashMultiset.create();
Set<Long> divisors = new HashSet<>();
``````Traditional=> [1, 2, 5, 10]