GRC for N numbers issue with StackOverflowException

Question

I'm trying to find GRC for N numbers. For example N = 4, so the 4 numbers is for example 199 199 -199 -199. And im getting StackOverflowException for those numbers. Why? first input number of integers for which i should find GRC. Second input number is array of numbers wroted in one line separeted by " ". Here is my code:

static int GCD(int a, int b)
    {
        if (b == 0) return a;
        if (a > b) return GCD(b, a - b);
        else return GCD(a, b-a);
    }

    static void Main()
    {
        var input = Convert.ToInt32(Console.ReadLine());
        int gcd;
        string readLine = Console.ReadLine();
        string[] stringArray = readLine.Split(' ');
        int[] intArray = new int[input];
        for (int i = 0; i < stringArray.Length; i++)
        {
            intArray[i] = int.Parse(stringArray[i]);
        }
        if (input >= 2)
        {
            gcd= Math.Abs(GCD(intArray[0], intArray[1]));
        }
        else
        {
            gcd= intArray[0];
        }

        for (int i = 2; i < input; i++)
        {
            gcd= Math.Abs(GCD(gcd, intArray[i]));
        }
        Console.WriteLine(Math.Abs(gcd));
        Console.ReadKey();
    }

Any suggestions how to improve the code?

Answer 1

First of all, it's unclear what is GRC. Your code is about GCD - Greatest Common Divisor. Let's improve its implementation.

If you have huge difference, beween a and b, say a = 1_000_000_000 and b = 1 you are going to have ~ a - b ~ 1_000_000_000 recursive calls in GCD and have Stack Overflow Exception.

Let's use modulo arithmetics instead: if a = b + b + ... + b + remainder, we can find remainder in one go, without subtracting b: remainder = a % b

Code:

static int GCD(int a, int b) 
{
    a = Math.Abs(a);
    b = Math.Abs(b);

    if (a == 0)
        return b; // b divides both 0 and itself
    if (b == 0)
        return a; // a divides both 0 and itself

    if (a % b == 0) // b divides both a and b, so b is GCD(a, b)
      return b;

    return GCD(b, a % b);    
}

then we can compute GCD for as many numbers as we want

static int GCD(IEnumerable<int> numbers) {
  if (numbers is null)
    throw new ArgumentNullException(nameof(numbers));

  int result = 0;

  foreach (var number in numbers) 
    if (result == 0)
      result = number;
    else 
      result = GCD(result, number); 
  
  return result != 0
    ? result
    : throw new ArgumentOutOfRangeException(nameof(numbers), "Empty sequence");
}

Usage: (fiddle)

using System.Linq;

...

static void Main() {
  int gcd = GCD(Console
    .ReadLine()
    .Split(' ', StringSplitOptions.RemoveEmptyEntries)
    .Select(item => int.Parse(item)));

  Console.Write(gcd);
}