例使用递归算法求m和n的最大公约数gcd 分析:求m和m的最大公约数等价于求n与( m mod n) 的最大公约数。 则有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) 的最大公约数。 则有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即为最大公约数