欧几里得——最大公约数 GCD

1、递归实现

int gcd(int a, int b) {

        if (b == 0) {//b=0的时候上个调用中的a%b等于零，那么对于上一个调用gcd(a,b)的最大公约数就是b，也就是下一个循环的a，直接返回即可

                return a;

        }

        return

                gcd(b, a % b);

}

2、非递归调用实现

int Gcd(int a, int b) {

        while (b != 0) {

                　　int r = b;

                　　b = a % b;

                　　a = r;

        }

        return a;

}