Optimizing recursive method

Question

I have some code that needs to run with some rather large numbers, and it involves incrementing into a recursive method and is therefor very slow to the point where I can't even get to my desired answer. Could someone help me optimize it? I am a beginner though, so I can't do anything very complex/difficult.

public class Euler012{
    public static void main(String[]args){
        int divisors=0;
        for(long x=1;divisors<=501;x++){
            divisors=1;
            long i=triangle(x);
            for(int n=1;n<=i/2;n++){
                if(i%n==0){
                    divisors++;
                }
            }
            //System.out.println(divisors+"\n"+ i);
            System.out.println(i+": " + divisors);
        }
    }
    public static long triangle(long x){
        long n=0;
        while(x>=0){
            n+=x;
            x--;
            triangle(x);
        }
        return n;
    }
 }

What is triangle(x) supposed to return? The recursive call in it seems like a bug, since you are always calling it with the same x value, so it will cause an infinite recursion. — Eran, Oct 19 '14 at 20:31
@Eran - The value is decremented just before the recursive call. — Don Roby, Oct 19 '14 at 20:34
@DonRoby Oh, I see. But, still, OP doesn't do anything with the return value of `triangle`, so what's the point of the recursive call? — Eran, Oct 19 '14 at 20:35
@Eran the function returns the next "triangle" number in the sequence. (with the return statement after the while loop). A triangle number n is the summation of every number up to and including n. — Seth, Oct 19 '14 at 20:40
I would like to know what your program should do and you don't need the >= check in your while condition > is enough — Soraphis, Oct 19 '14 at 20:46
If you are concerned about optimisation, you can go for the O(1) approach and use the function `public static long triangle(long x){ return (x*x + x)/2; }` — Richard Kenneth Niescior, Oct 19 '14 at 20:47
@RichardKennethNiescior could you please explain your function? I'm not sure I understand how that is the same as my triangle method — Seth, Oct 19 '14 at 20:53
@seth Fundamentally your triangle method is a summation of a dynamic value being decremented by one as it approaches zero. So, lets take this for example, `triangle(5)` is O(5) as it requires 5 iterations to complete the computation, thus it would be the following process (5 + 4 + 3 + 2 + 1) == 15 right? It runs through multiple instructions where as the suggestion I provided, gives you O(1) instance where there are **no redundant iterations** as ((5 * 5 + 5)/2) == 15. Get the picture? It is about minimising the number of instructions required to perform the computation. — Richard Kenneth Niescior, Oct 19 '14 at 20:59
@seth it is the same, its the gaussian summation formula - dont know the correct name in english. You can test the formular with a few numbers and i can proof it if you want — Soraphis, Oct 19 '14 at 21:02

score 1 · Accepted Answer · edited May 23 '17 at 12:07

First: i don't think its an optimization problem, because its a small task, but as mentioned in the comments you do many unnecessary things.

Ok, now lets see where you can optimize things:

recursion

recursion has usually a bad performance, especially if you don't save values this would be possible in your example.

e.g.: recursive triangle-number function with saving values

private static ArrayList<Integer> trianglenumbers = new ArrayList<>();

public static int triangleNumber(int n){
    if(trianglenumbers.size() <= n){
        if(n == 1)
            trianglenumbers.add(1);
        else
            trianglenumbers.add(triangleNumber(n-1) + n);
    }
    return trianglenumbers.get(n-1);
}

but as mentioned by @RichardKennethNiescior you can simply use the formula: (n² + n)/2

but here we can do optimization too! you shouldnt do /2 but rather *0.5 or even >>1(shift right) but most compilers will do that for you, so no need to make your code unreadable

your main method

public static void main(String[]args){
    int divisors = 0; //skip the = 0
    for(long x=1;divisors<=501;++x){ // ++x instead of x++
        divisors=0;
        long i=(x*x + x) >> 1; // see above, use the one you like more
        /*how many divisors*/
        if(i == 1) divisors = 1;
        else{ /*1 is the only number with just one natural divisor*/
            divisors = 2; // the 1 and itself
            for(int n = 2; n*n <= i; ++n){
                if(n*n == i) ++divisors;
                else if(i%n == 0) divisors += 2;
            }
        }
        System.out.println(i+": " + divisors);
    }
}

the ++x instead of x++ thing is explained here

the how many divisors part: every number except 1 has at least 2 divisors (primes, the number itself and one) to check how many divisors a number has, we just need to go to the root of the number (eg. 36 -> its squareroot is 6) 36 has 9 divisors (4 pares) {1 and 36, 2 and 18, 3 and 12, 4 and 8, 6 (and 6)}

1 and 36 are skiped (for(**int n = 2**)) but counted in divisors = 2 and the pares 2, 3 and 4 increase the number of divisors by 2 and if its a square number (n*n == i) then we add up 1

score 0 · Answer 2 · answered Oct 20 '14 at 00:48

0

You dont have to generate a new triangle number from scratch each time, if you save the value to a variable, and then add x to it on the next iteration, you dont really need to have the triangle method at all.

answered Oct 20 '14 at 00:48

spyr03

864
1
8
27

Optimizing recursive method

2 Answers2

recursion

your main method