c++ ，递归函数 ，读程序

来源：百度知道 编辑：UC知道 时间：2024/05/24 16:12:16
Gcf(int m,int n)
{
if(n==0)
return m;
else
return Gcf(n,m%n);
}
这段程序什么意思啊？

在数学上有一种求两数a,b最小公约数的方法，
步骤一:a除以b(即a÷b)，c是余数。
步骤二:如果c不等于0，那么将b赋值给a，c赋值给b，重复步骤一。如果c等于0，那么跳转至步骤三。
步骤三:步骤二中的b的值即a与b的最小公约数。
上述函数的功能即最小公约数算法思想的实现。

例:求48和14的最小公约数
(1)48÷14=3余6 余数不为0
(2)14÷6=2 余2 余数不为0
(3) 6÷2=3 余0 余数为0，结束
48和14的最小公约数是2.

求最大公约数的问题。这里用的是辗转相除法

举例：120 84

return Gcf(84, 36)
return Gcf(36, 12)
return Gcf(12, 0 )
return 12

辗转相除法

比如，求48，36的最大公约数
m n
48，36
36，12 (12 = 48除以36的余数)
12，0 ( 0 = 36除以12的余数)

n为0，返回12

是求两个数的最大公约数。