利用递归与数学方法求解最大公约数与最小公倍数问题

解题思路:
在求解此题前我们需要先明白最大公约数与最小公倍数应该怎么求

1、最大公约数可用辗转相除法求解：

例如：288和123

288%123=2......42(此处得到42以备用)

123%42=2......39(此处得到39以备用)

42%39=1......3

39%3=13......0

那么此时，可以得到3就是288与123的最大公约数（百度上对辗转相除法有更详细的解释，但大概就是我写的这样，用两数中的较大数（288）取模较小数（123），得出的结果（42）作为下一项较小数，再把本项的较小数（123）作为下一项的较大数以此往复，直到余数为0，此时的较小数就是最开始两数的最大公约数）

2、最小公倍数可用公式法求解：

例如：288和123

最小公倍数=288*123/最大公约数（根据1可求出最大公约数为3）

在明白这两点后就可用递归的方法来求解此题了

注意事项:

在创建递归函数时需要依次传入两数中的较大数和较小数，同时需要额外传入一个中间变量用于接收较小数

参考代码:

#include<iostream>

using namespace std;

int dfs(int a, int b,int temp)//利用递归和辗转相除求解出最大公约数，其中temp为接收较小数b的中间变量

{

    if(b==0)//设置退出条件为最后得到的余数为0，即在下一项是  a/b  中b=0时，则返回此时的a值即为最大公约数

    {

        return a;

    }

    temp = b;//提前存储b值以便后续使用

    b = a % b;//把两数的余数当作下一项的b值

    a = temp;//把上一项的b值当作下一项的a值

    dfs(a, b, temp);//继续递归直到满足退出条件

}

int main()

{

    int a, b;

    cin >> a >> b;

    int c = max(a, b);//找出两数中的较大数

    int d = min(a, b);//找出两数中的较小数

    cout << dfs(c, d, 0) << " " << a * b / dfs(c, d, 0);//第一项输出最大公约数，第二项用公式法输出最小公倍数

    return 0;

}