求最大公约数

摘自《算法》

描述

计算两个非负整数p和q的最大公约数：若q是0，则最大公约数为p。否则，将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数。

实现

public static int gcd(int q,int p){
    if(q==0) return p;
    int r= p%q;
    return gcd(q,r)
}

递归要点

1. 总有一个最简单的情况——方法的第一条语句总是一个包含return的条件语句
2. 递归调用总是去尝试解决一个规模更小的子问题，使得问题往最简单的情况收敛
3. 递归调用的父问题和尝试解决的子问题之间不应该有交集