Write a recursive function which returns the gcd of two integers m and n given that

   Given that gcd(n, m) = gcd(n, m mod n)

Source Code

Brief explanation is provided after the source code.

#include <stdio.h>

int gcd(int, int);

int main(int argc, char ** argv) {
    int n, m;
    printf("Input integer n: ");
    scanf("%d", &n);
    printf("Input integer m: ");
    scanf("%d", &m);
    printf("gcd is: %d", gcd(n, m));
    return 0;
}

/* Recursive function */
int gcd(int n, int m) {
    if (n == 0)
        return m;
    else if (m == 0)
        return n;
    else {
        return gcd(m, n % m);
    }
}

When you compile and execute the above program it produces the following result on Linux:

Input integer n: 8
Input integer m: 4
gcd is: 4

Brief Explanation

  • The greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4. More on Greatest common divisor
  • A recursive function is a function that calls itself during its execution. This enables the function to repeat itself several times, outputting the result at the end of each iteration. More on Recursive Function
  • The program starts by requesting the two integers whose gcd we want to return.
  • The function gcd is a recursive function that takes the two integers as parameters and return the gcd. If one of the integer (e.g n) is zero, then the other is returned as the gcd and vice versa otherwise the function calls itself repeatedly taking the integer m and the modulo of n and m as parameters. The function will call itself repeatedly until one of the parameters is zero and at which point the gcd will be returned to the main program.
  • Using the printf function, the gcd is printed to the output screen.

Add comment


Security code
Refresh