/* 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]);

}