logic behind this method - 1420

this was in the community help section where people posted asking for help. actually, quite a number of them had this method. I don't know if they all know this little trick or just copied/pasted?? don't know. I hope someone answers.

That's the Euclidean algorithm. So it's from a really smart guy ;) You can read about it on wikipedia with coding examples including this recursive attempt. I used it as well cause I remembered it from school (but had to look it up again in the web to remeber exactly how it works). You can find lots of coding examples in the web (recursive and non recursive - the latter may be a good starting point to explore it more).

facinating stuff. Again, thanx Thomas for the reply/input. I guess I could apply it if I ever need to get a GCD in the future. As far as fully understanding the logic, I will have to save for a later time so I can continue to cover CG's material.

The logic behind the algorithm is very simple. Take two numbers, a and b, find the remainder after division, then make 'a' equal 'b' and 'b' equal the remainder. Repeat those steps until the remainder equals 0, and the answer will be a:

int a = /*any number*/;
int b = /*any number*/;
int remainder = 1; // set remainder to anything other than 0
while(remainder != 0) { // loop while remainder does not equals 0
    remainder = a % b; // find remainder after division (modulo operator)
    a = b; // make a equal b
    b = remainder;  //make b equal remainder
}
// at this point the correct answer is 'a'

Personally, recursion is just a parlor trick that looks cool but 99.99% of the time is inferior to a loop. This is because every method call takes up memory on the stack and having too many unresolved methods can lead to a massive amount of memory being used very easily. Too many method calls on the stack will result in a stack overflow error. Take this code as an example:

class Solution {
    public static void main(String[] args) {
        infiniteLoop();
        infiniteRecursion();
    }

    static void infiniteLoop() {
        while(true);
    }

    static void infiniteRecursion() {
        infiniteRecursion();
    }
}

Run the code as is and it will enter an infinite loop. You could leave your computer for a couple hours and when you come back the loop would still be going. Comment out line 3 and run the program again. In less than a second a StackOverflowError will occur, meaning the program completely filled all memory allocated to the stack, and the program will end.