例使用递归算法求m和n的最大公约数gcd 分析:求m和m的最大公约数等价于求n与( m mod n) 的最大公约数。(mod模运算即整除求余) 则有gcd(m,n)等价于gcd(n,( m mod n) 例如:求24和16的最大公约数 即求与gcd(16,(24mod16)的最大公约数 为 gcd(16,8 又等价于gcd(16,(16mod8) 为gcd(8,0) 此时n为零,m即为最大公约数例 使用递归算法求m和n的最大公约数gcd 分析：求m和n的最大公约数等价于求n与(m mod n) 的最大公约数。（ mod 模运算即整除求余） 则有gcd(m, n)等价于gcd(n, (m mod n)) 例如：求24和16的最大公约数 即求与gcd(16, (24 mod 16))的最大公约数 为gcd(16,8) 又等价于gcd(16, (16 mod 8)) 为gcd(8,0) 此时n为零，m即为最大公约数