Question: Write a program to find Greatest Common Divisor(GCD) of two numbers using recursion.
Explanation:
Rule 01: if(b==0) return GCD(a,b)=a;
Rule 02: else if(a>b) return GCD(a,b)=GCD(b,a);
Rule 03: else return GCD(a,b%a);
You can also see for video explanation
| a=3 b=5 GCD(3,5) = GCD(3, 2) Rule 03 GCD(3,2)=GCD(2,3) Rule 02 GCD(2,3)=GCD(2,1) Rule 03 GCD(2,1)=GCD(1,2) Rule 02 GCD(1,2)=GCD(1,0) Rule 03 GCD(1,0) = 1 Rule 01 |
Program:
<include<bits/stdc++.h>
int GCD(int,int); ///Function Prototype
int main()
{
int a,b,result;
while(scanf(“%d %d”,&a,&b)==2)
{
result=GCD(a,b); ///Function Calling
printf(“GCD of %d and %d is: %d\n”,a,b,result);
}
return 0;
}
int GCD(int p,int q) ///Function/Recursion Definition
{
if(q==0)
return p;
else if(p>q)
return GCD(q,p);
else
return GCD(p,q%p);
return -1;
}