How do I print the Greatest Common Divisor using recursion?

Question

I am trying to write a code to calculate the GCD (Greatest Common Divisor) of two numbers using recursion.

Although that I can print the common divisors of the numbers, I am struggling to print the GCD.

This is what I have to print the common divisors:

#include <stdio.h>

void gcd(int num1, int num2, int i) {
    int x;
    int small = (num1 < num2) ? num1 : num2;
    if (i == small) {
        return;
    } else {
        if (num1 % i == 0 && num2 % i == 0) {
            x = i;
           printf("%d ", x);
        }
        gcd(num1, num2, i + 1);
    }
    
}

int main() {
    int num1, num2, i;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    i = 1;
    gcd(num1, num2, i);
    return 0;
}

Now I have to print the GCD. But when I run the following program I get random outputs (address maybe). How do I solve this problem?

This is what I have so far to print the GCD:

#include <stdio.h>

void gcd(int num1, int num2, int i) {
    int x;
    int small = (num1 < num2) ? num1 : num2;
    if (i == small) {
        return;
    } else {
        if (num1 % i == 0 && num2 % i == 0) {
            x = i;
           
        }
        gcd(num1, num2, i + 1);
    }
   printf("%d ", x);
}

int main() {
    int num1, num2, i;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    i = 1;
    gcd(num1, num2, i);
    return 0;
}

Answer 1

The recursive implementation in C of GCD is (Euclid: around 300 BC):

#include <stdio.h>

int gcd(int a, int b)
{
    int rem = a % b;
    return rem != 0
        ? gcd(b, rem)
        : b;
} /* gcd */

int main()
{
#define P(a, b)                        \
        printf("P(%d, %d) -> %d\n",    \
                   a,  b,    gcd(a, b))
    P(8, 6);
    P(8, 16);
    P(7, 24);
} /* main */

I cannot guess where did you get what you write in your question. My apologies for it.

Answer 2

From my archives. Don't know where I get it from.

unsigned int gcd(unsigned int a, unsigned int b) {
  if(b) return(gcd(b, a % b));
  return(a);
}

Answer 3

Problems

I understand that in your first code, you want to consider the numbers from 1 to the smaller number and find the common divisor. But as you use if (i == small), the function gcd would return when i equals to the smaller number. That means the function wouldn't output the GCD when one number is exactly a multiple of another number (e.g. 6 and 12). Therefore you should use if (i > small).

Another problem in your code is in your second code, as pointed in the comment section, the value of x is undefined, so the program may output undefined values (e.g. 2097184), and that's why you get random outputs. Therefore you should probably initialize x, like int x = 0;.

Solution

I suggest you to use a function with a return value, because the return value can join other calculations and creates portability.

One of the solution is just find the common divisors, and then find the greatest one.
You can still use your function gcd(int num1, int num2, int i), but you can let it to have a return value means the greatest number from i to the smaller number that is the common divisor of the two numbers, and the return value 0 means the is no number meet the conditions above.
The source code:

#include <stdio.h>

int gcd(int num1, int num2, int i) {
    int x = 0, y;
    int small = (num1 < num2) ? num1 : num2;
    if (i > small) {
        return 0;
    } else {
        if (num1 % i == 0 && num2 % i == 0) {
            x = i;
        }
        y=gcd(num1,num2,i + 1);
        return (x > y) ? x : y;
    }
}

int main() {
    int num1, num2, i;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    i = 1;
    printf("%d",gcd(num1, num2, i));
    return 0;
}

Another method to solve the problem is using the Euclid algorithm, as mentioned in the comment section, it can be expressed in the following statement:

gcd(a, b) = gcd(b, a%b) (a >= b)

So, we can use a gcd(int num1, int num2) function and let the gcd function to return gcd(num2, num1 % num2) when num1 >= num2.
But what to do when one of the numbers is 0? We return the other number.
Based on the content above, we can write the following source code:

#include <stdio.h>

int gcd(int num1, int num2) {
    if (num1 == 0) {
        return num2;
    } else if (num2 == 0) {
        return num1;
    } else {
        return gcd(num2, num1 % num2);
    }
}

int main() {
    int num1, num2;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    printf("%d",gcd(num1, num2));
    return 0;
}

In the question it asks to calculate the GCD using recursion, but the problem can also be solved by loops. Actually, I think that it would will be easier to write and understand if you use loops to solve the problem. Of course, it would be good to understand other methods and the logic thoughts behind.
This a simple example of using loops:

#include <stdio.h>

int gcd(int num1, int num2) {
    int small = (num1 > num2) ? num1 : num2, i;
    for (i = small; i >= 1; i--) {
        if (num1 % i == 0 && num2 % i == 0) {
            return i;
        }
    }
}

int main() {
    int num1, num2;
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    printf("%d",gcd(num1, num2));
    return 0;
}

Conclusion

Some possible solutions of the problem are listed above.