Error when I use recursion to get more than 4 perfect numbers JAVA

Question

I'm using an algorithm with recursion to calculate 30 perfect numbers, but only calculates the first 4 and then the program throws an error.

public class PerfectNumbers {
  /**
  * @param args the command line arguments
  */
  public static void main(String[] args) {
    getPerfectNumbers(1,1);
  }

  static void getPerfectNumbers(long out,long number) {
    long total = 0;
    if(out==30) {
      return;
    }
    for ( int i=1;i<number;i++) {
      if(number%i==0) {
        total+=i;
      }
    }
    if(total==number) {
      System.out.println("Perfect Number "+number);
      out++;
    }
    number++;
    getPerfectNumbers(out,number);  
  }
}

What's wrong with the algorithm?

It is not that it never ends, the size of the iterations is very large, it is something completely different, because the logic is correct. — Andres Salazar Lopez, May 25 '18 at 19:12

davidxxx · Accepted Answer · 2018-05-25T17:15:55.160

The perfect numbers start by :

6, 28, 496, 8128, 33550336

Performing 8128 nested invocations with a method that accepts two long parameter is generally feasible for the JVM.
I precise "two parameters" as the size of the stack matters in the number of nested invocation accepted by the JVM.
But from a some level of nested invocation, the JVM throws an Error : java.lang.StackOverflowError that is defined as :

Thrown when a stack overflow occurs because an application recurses too deeply.

And 33550336 invocations nested are bound to be too much.

The algorithm is probably correct but you should favor loop over recursivity to prevent the overflow of the stack.

score 1 · Answer 2 · answered May 25 '18 at 17:13

The 5th perfect number is so big that the amount of recursions it takes to reach it results in a StackOverflowError. Manually checking every single number technically works, but is far from optimal as even the 5th perfect number is 33550336, which would take far longer than reasonable to calculate. A more efficient technique would be to check if the number can be represented by 2^(p-1)*(2^p-1), where p and 2^p-1 are prime. However, with that said, you are almost certainly going to be unable to calculate 8 perfect numbers, let alone 30, with a recursive or loop technique, simply because the numbers get far too big very quickly.

Error when I use recursion to get more than 4 perfect numbers JAVA

2 Answers2