Implementing Euclid's Algorithm in Java

Question

I've been trying to implement Euclid's algorithm in Java for 2 numbers or more.The problem with my code is that

a) It works fine for 2 numbers,but returns the correct value multiple times when more than 2 numbers are entered.My guess is that this is probably because of the return statements in my code.

b) I don't quite understand how it works.Though I coded it myself,I don't quite understand how the return statements are working.

import java.util.*;

public class GCDCalc {

static int big, small, remainder, gcd;

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // Remove duplicates from the arraylist containing the user input.

    ArrayList<Integer> listofnum = new ArrayList();
    System.out.println("GCD Calculator");
    System.out.println("Enter the number of values you want to calculate the GCD of: ");
    int counter = sc.nextInt();

    for (int i = 0; i < counter; i++) {
        System.out.println("Enter #" + (i + 1) + ": ");
        int val = sc.nextInt();
        listofnum.add(val);
    }

    // Sorting algorithm.
    // This removed the need of conditional statements(we don't have to
    // check if the 1st number is greater than the 2nd element
    // before applying Euclid's algorithm.
    // The outer loop ensures that the maximum number of swaps are occurred.
    // It ensures the implementation of the swapping process as many times
    // as there are numbers in the array.
    for (int i = 0; i < listofnum.size(); i++) {
        // The inner loop performs the swapping.
        for (int j = 1; j < listofnum.size(); j++) {
            if (listofnum.get(j - 1) > listofnum.get(j)) {
                int dummyvar = listofnum.get(j);
                int dummyvar2 = listofnum.get(j - 1);
                listofnum.set(j - 1, dummyvar);
                listofnum.set(j, dummyvar2);

            }
        }
    }

    // nodup contains the array containing the userinput,without any
    // duplicates.
    ArrayList<Integer> nodup = new ArrayList();
    // Remove duplicates.
    for (int i = 0; i < listofnum.size(); i++) {
        if (!nodup.contains(listofnum.get(i))) {
            nodup.add(listofnum.get(i));
        }
    }

    // Since the array is sorted in ascending order,we can easily determine
    // which of the indexes has the bigger and smaller values.
    small = nodup.get(0);
    big = nodup.get(1);
    remainder = big % small;

    if (nodup.size() == 2) {
        recursion(big, small, remainder);
    } else if (nodup.size() > 2) {
        largerlist(nodup, big, small, 2);
    } else // In the case,the array only consists of one value.
    {
        System.out.println("GCD: " + nodup.get(0));
    }
}

// recursive method.
public static int recursion(int big, int small, int remainder) {
    remainder = big % small;
    if (remainder == 0) {
        System.out.println(small);
    } else {
        int dummyvar = remainder;
        big = small;
        small = dummyvar;
        recursion(big, small, remainder);
    }
    return small;
}

// Method to deal with more than 2 numbers.
public static void largerlist(ArrayList<Integer> list, int big, int small, int counter) {
    remainder = big % small;
    gcd = recursion(big, small, remainder);

    if (counter == list.size()) {

    } else if (counter != list.size()) {
        big = gcd;
        small = list.get(counter);
        counter++;
        largerlist(list, gcd, small, counter);
    }

  }
}

I apologize in advance for any formatting errors etc. Any suggestions would be appreciated.Thanks!

Answer 1

I think these two assignments are the wrong way around

    big = gcd;
    small = list.get(counter);

and then big not used

    largerlist(list, gcd, small, counter);

Also you've used static variables, which is usually a problem.

I suggest removing static/global variables and generally don't reuse variables.

Edit: Oh yes, return. You've ignored the return value of the recursion method when called from the recursion method. That shouldn't matter as you are printing out instead of returning the value, but such solutions break when, say, you want to use the function more than once.