递归解决简单问题（2022-02-02）

package demo;

public class P13 {
    
    public static void main(String[] args) {
        System.out.println(fib(5));
    }
    
    //求斐波那契数列的第n个数字
    static int fib(int n) {
        if(n==1 || n==2)
            return 1;
        return fib(n-1)+fib(n-2);
    }
    
    //求m,n的最大公约数(gcd)
    //原理：辗转相除法，m%n==0则n就是最大公约数，否则gcd(m,n)等价于gcd(n,m%n)
    static int gcd(int m,int n) {
        if(n==0)
            return m;
        return gcd(n, m%n);
    }
}