#include "gcd.h"
#include <assert.h>

// when this is called, i and j are positive, j is no bigger than i, 
// and i is not zero.

static int gcdRecur(int i, int j) {
  if(j == 0) {
    return i;
  }

  return gcdRecur(j, i%j);
}
  

int GreatestCommonDivisor(int i, int j) {
  assert(i || j); // make sure at least one number is not zero

  if(i < 0) {
    i = -i;
  }
  if(j < 0) {
    j = -j;
  }

  // i and j are now non-negative

  if(i < j) {
    return gcdRecur(j, i);
  } else {
    return gcdRecur(i, j);
  }
}