Study For Your Career

Ans. The greatest common divisor of two positive integers is the largest integer that is a divisor of both of them. For, example, 3 is the greatest common divisor of 6 and 15, and 1 is the greatest common divisor of 7 and 11.

Hence , here is a recursive function that computest the greatest common divisor of two positive integers:

// in file gcd.c
#include<stdio.h>
#include <conio.h>


int gcd ( int a, int b ) {
    int r;
    if ( ( r = a%b ) == 0 )
       return b;
    else
       return gcd ( b , r );
}

void main(void){
   int p,q;
   printf("\n Enter two numbers: ");
   scanf("%d %d",&p,&q);
   printf("\n The gcd is  %d ",gcd(p,q));
   getch( );
}

________
For ex: if a=15 and b=6 , then
   (r = 3) !=0 hence again the func executes with value a=6 , b=3
   Now , the value of r become 0 .
   Hence the value of b ,(i.e) 3 , is returned .

Please post if you have a better solution.