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
– Eran, Commented Oct 19, 2014 at 20:31
@Eran - The value is decremented just before the recursive call. — Don Roby
– Don Roby, Commented Oct 19, 2014 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
– Eran, Commented Oct 19, 2014 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
– Seth, Commented Oct 19, 2014 at 20:40

Community · Accepted Answer · 2017-05-23 12:07:16Z

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

spyr03 · Accepted Answer · 2014-10-20 00:48:26Z

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, 2014 at 0:48

spyr03

8821 gold badge8 silver badges28 bronze badges

Collectives™ on Stack Overflow

Optimizing recursive method

2 Answers 2

recursion

your main method

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

recursion

your main method

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related