Recursion | GCD | Euclids Algorithm | Lecture 31 | Java & DSA Course

J    A    V     A               C    O     D     E

  1. Write a program to find Greatest Common Deviser (GCD) by using Recursion  

    </>   RecGcd1.java    

// BRUTE FORCE APPROACH

package Recursion;
import java.util.Scanner;

public class RecGcd1 {
     public static int find(int x,int n1,int n2){
          if(n1%x==0 && n2%x==0)
               return x;
          return find(x-1,n1,n2);
     }
     public static void main(String[] args) {
          Scanner sc=new Scanner(System.in);
          System.out.println("Enter n1 and n2");
          int n1=sc.nextInt();
          int n2=sc.nextInt();
          int x;
          if(n1<=n2) x=n1;
          else x=n2;
          int ans=find(x,n1,n2);
          System.out.println(ans);

          sc.close();
     }
}

   2. Writing this GCD program by Second Method    

   </>  RecGCDbyLongDivision.java   

// BY LONG DIVISION CONCEPT :

package Recursion;
import java.util.Scanner;

public class RecGCDbyLongDivision {
     public static int gcd(int s,int b){

          if(s==0) return b;
          return gcd(b%s,s);

     }
     public static void main(String[] args) {
          Scanner sc=new Scanner(System.in);
          System.out.println("Enter x and y: ");
          int x=sc.nextInt();
          int y=sc.nextInt();
          int s,b;
          if(x<y){
               s=x;
               b=y;
          }
          else{
               s=y;
               b=x;
          }

          int ans=gcd(s,b);
          System.out.println("gcd of "+x+" and"+y+" is :"+ans);
          sc.close();
     }
}

    3. Writing previous program by using EUCLID ALGORITHM     

   </>    RecGCDbyEuclidAlgorithm.java    

// BY LONG DIVISION CONCEPT :

package Recursion;
import java.util.Scanner;

public class RecGCDbyEuclidAlgorithm {
     public static int gcd(int x,int y){

          if(y==0) return x;
          return gcd(y,x%y);

     }
     public static void main(String[] args) {
          Scanner sc=new Scanner(System.in);
          System.out.println("Enter x and y: ");
          int x=sc.nextInt();
          int y=sc.nextInt();

          int ans=gcd(x,y);
          System.out.println("gcd of "+x+" and"+y+" is :"+ans);
          sc.close();
     }
}

      4. Write a program to finding LCM  by using Recursion      

     </>   RecLCM.java     

// WE KNOW THAT  :   lcm(x,y)= (x*y)/gcd(x,y)

package Recursion;
import java.util.Scanner;

public class RecLCM {
     public static int lcm(int x,int y){
          if(y==0) return x;
          return lcm(y,x%y);
     }
     public static void main(String[] args) {
          Scanner sc=new Scanner(System.in);
          System.out.println("Enter x and y: ");
          int x=sc.nextInt();
          int y=sc.nextInt();
          int ans=lcm(x,y);
          System.out.println("LCM of "+x+" and "+y+" is: "+(x*y)/ans);

          sc.close();
     }
}

      5. Write a program to check  ArmStrong Number      

    </>   RecArmStrongNum.java   

package Recursion;
import java.util.Scanner;

public class RecArmStrongNum {

     // Methods for finding POWER :
     public static int power(int d,int i){
          if(i==0) return 1;
          int x=power(d,i/2);
          if(i%2==0)
               return x*x;
          else
               return d*x*x;

     }

     // Methods for finding ARMstrong :
     public static int checking(int num,int i,int count){
          if(count==0) return 0;
          return power(num%10,i)+checking(num/10,i,count-1);
     }

     // MAIN METHOD :
     public static void main(String[] args) {
          Scanner sc=new Scanner(System.in);
               System.out.println("Enter a number : ");
               int n=sc.nextInt();
               int num=n;
               // finding number of digits ( 'i' denotes no. of digit )
               int i=0;
               for(;n>0;i++) n/=10;
          int count=i;
          int ans=checking(num,i,count);
          if(num==ans)
               System.out.println("Y E S , "+num+" is an ARM Strong number");
          else
               System.out.println("N O , "+num+" is not a ARM Strong number");
               sc.close();

     }
}

      6. Write a program to find a Simple Product       

     </>     RecSimpleMultiply.java    
// SIMPLE PRODUCT :

package Recursion;
import java.util.Scanner;

public class RecSimpleMultiply {
     public static int multi(int a,int b){
          if(b==0) return 0;
          return a+multi(a,b-1);
     }
     public static void main(String[] args) {
          Scanner sc=new Scanner(System.in);
          System.out.println("Enter a and b: ");
          int a=sc.nextInt();
          int b=sc.nextInt();
          int ans=multi(a,b);

          sc.close();
     }
}

-  SEE   YOU   AGAIN   !!