Chương trình Java để tìm G.C.D bằng cách sử dụng đệ quy

Trong bài này, chúng ta sẽ hiểu cách tìm G.C.D bằng cách sử dụng đệ quy. Một hàm đệ quy là một hàm gọi chính nó nhiều lần cho đến khi một điều kiện cụ thể được thỏa mãn. Số chia chung lớn nhất (GCD) của hai số là số lớn nhất mà chia cả hai số đó.

Đệ quy là quá trình lặp lại các mục theo cách tương tự. Trong ngôn ngữ lập trình, nếu một chương trình cho phép bạn gọi một hàm bên trong cùng một hàm, thì nó được gọi là lệnh gọi đệ quy của hàm.

Nhiều ngôn ngữ lập trình thực hiện đệ quy bằng các ngăn xếp. Nói chung, bất cứ khi nào một hàm (người gọi) gọi một hàm khác (callee) hoặc chính nó là callee, thì hàm người gọi sẽ chuyển quyền kiểm soát thực thi đến callee. Quá trình chuyển này cũng có thể liên quan đến một số dữ liệu được chuyển từ người gọi đến người gọi.

Dưới đây là một minh chứng về điều tương tự -

Đầu vào

Giả sử đầu vào của chúng tôi là -

Enter two numbers: 24 and 36

Đầu ra

Đầu ra mong muốn sẽ là -

The G.C.D of 24 and 36 is 12.

Thuật toán

Step 1 - START
Step 2 - Declare three values namely my_input_1, my_input_2 and my_result
Step 3 - Read the required values from the user/ define the values
Step 4 - A recursive function ‘CommonFactor’ is defined which takes two integers as input and returns two values i.e ‘my_input_2’ value and ‘my_input_1’ % ‘my_input_2’ value.
Step 5 - The function is called recursively until the value of ‘my_input_2’ is greater than 0. Store the result.
Step 6 - Display the result
Step 7 - Stop

Ví dụ 1

Ở đây, đầu vào đang được người dùng nhập dựa trên lời nhắc. Bạn có thể thử trực tiếp ví dụ này trong công cụ nền tảng mã hóa của chúng tôi .

import java.util.Scanner;
public class GCD {
   public static void main(String[] args) {
      int my_input_1, my_input_2, my_result;
      System.out.println("Required packages have been imported");
      Scanner my_scanner = new Scanner(System.in);
      System.out.println("A reader object has been defined ");
      System.out.print("Enter the first number : ");
      my_input_1 = my_scanner.nextInt();
      System.out.print("Enter the second number : ");
      my_input_2 = my_scanner.nextInt();
      my_result = CommonFactor(my_input_1, my_input_2);
      System.out.printf("The G.C.D of %d and %d is %d.", my_input_1, my_input_2, my_result);
   }
   public static int CommonFactor(int my_input_1, int my_input_2){
      if (my_input_2 != 0)
         return CommonFactor(my_input_2, my_input_1 % my_input_2);
      else
         return my_input_1;
   }
}

Đầu ra

Required packages have been imported
A reader object has been defined
Enter the first number : 24
Enter the second number : 36
The G.C.D of 24 and 36 is 12.

Ví dụ 2

Ở đây, số nguyên đã được xác định trước đó và giá trị của nó được truy cập và hiển thị trên bảng điều khiển.

public class GCD {
   public static void main(String[] args) {
      int my_input_1, my_input_2, my_result;
      my_input_1 = 24;
      my_input_2 = 36;
      System.out.println("The numbers are defined as " +my_input_1 +" and " +my_input_2);
      my_result = CommonFactor(my_input_1, my_input_2);
      System.out.printf("The G.C.D of %d and %d is %d.", my_input_1, my_input_2, my_result);
   }
   public static int CommonFactor(int my_input_1, int my_input_2){
      if (my_input_2 != 0)
         return CommonFactor(my_input_2, my_input_1 % my_input_2);
      else
         return my_input_1;
   }
}

Đầu ra

The numbers is defined as 24 and 36
The G.C.D of 24 and 36 is 12.