博客

递归实现两个正整数的最大公约数与最小公倍数：

递归：方法定义中调用方法本身的现象

注意事项：1、递归一定要有出口，否则此递归就是一个死递归

2、递归的次数不能太多，否则会内存溢出

3、构造方法不能使用递归

import java.util.Scanner;

/**
 * 辗转相除法
 * 递归求最大公约数与最小公倍数
 */
public class RecGcd {
    public static void main(String[] args) {
        System.out.println("请您分别输入两个正整数:");
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        if(n<m) {
            m = m+n;
            n = m-n;
            m = m-n;
            print(m,n);
        }else if(n>m) {
            print(m,n);
        }else{
            System.out.println(m+"和"+n+"的最大公约数是:1");
            System.out.println(m+"和"+n+"的最小公倍数是:"+m*n);
        }

    }

    private  static void print(int m,int n) {
        System.out.println(m+"和"+n+"的最大公约数是:"+gcd(m,n));
        System.out.println(m+"和"+n+"的最小公倍数是:"+m*n/gcd(m,n));
    }

    private static int gcd(int m, int n) {
        int temp = m % n;
        if(temp == 0) {
            return n;
        }else{
            return gcd(n,temp);
        }
    }
}