
GCD For all of You!
/* This programs makes use of recursion to calculate the GCD of N integers
By no means is intended to be a perfect program, there might be many other
ways (perhaps better) to do it, yet, I decided to post to help those who
are initiating in recursion and perhaps find it useful.
Author: Nicolas Raitman
Email: elrancha@hotmail.com
*/
#include <stdio.h>
#include <malloc.h>
#define EXIT_OK 1
#define EXIT_LESS_THAN_TWO 1
int processNumbers (int *, int);
int calculateGCD (int, int);
void showNumbers (int *, int);
int main (void)
{
int * iNumbers, iHowMany;
int iIndex;
printf("How many Numbers: "); scanf("%i", &iHowMany);
if (iHowMany < 2)
{
printf("To find the GCD you must enter at least two numbers.");
printf("Program Termination...");
return EXIT_LESS_THAN_TWO;
}
/* we allocate memory for the array that will contain N integers */
iNumbers = (int *) malloc (sizeof(int) * iHowMany);
/* we prompt the user to enter the values */
for (iIndex = 0; iIndex < iHowMany; iIndex++)
{
printf("Value #%i: ", (iIndex + 1));
scanf("%i", &(iNumbers[iIndex]));
}
printf("Greates Common Divisor between");
showNumbers(iNumbers, iHowMany);
printf (" is: %d", processNumbers(iNumbers, iHowMany));
return EXIT_OK;
}
int processNumbers (int * iNumbers, int iTotalNumbers)
{
int iIndex, iRes = iNumbers[0];
/* first: we calculate the GCD between the first and next one
second: we calculate the GCD between the GCD of the first and the
second and the third, and so on...
Finally, we calculate the GCD of the GCD of all previous numbers
and the final number.
Confused? Try running the program a couple of times and then try to
trace the program and you will see how it works.
*/
for (iIndex = 0; iIndex < iTotalNumbers  1; iIndex++)
iRes = calculateGCD(calculateGCD(iRes, iNumbers[iIndex + 1]), iNumbers[iIndex + 1]);
return calculateGCD(iRes, iNumbers[iIndex]);
}
int calculateGCD (int iFirst, int iSecond)
{
/* by definition, the GCD of two numbers is the following */
if (iFirst == 0)
return iSecond;
else
return calculateGCD((iSecond % iFirst), iFirst);
}
void showNumbers (int * iNumbers, int iTotalNumbers)
{
/* this function shows the values addresses by the iNumbers
pointer, so that the user can know between which numbers the GCD
operation is being performed */
int iIndex;
for (iIndex = 0; iIndex < iTotalNumbers; iIndex++)
printf(" %i", iNumbers[iIndex]);
}