package demo;

public class P13 {
    
    public static void main(String[] args) {
        System.out.println(fib(5));
    }
    
    //求斐波那契數(shù)列的第n個(gè)數(shù)字
    static int fib(int n) {
        if(n==1 || n==2)
            return 1;
        return fib(n-1)+fib(n-2);
    }
    
    //求m,n的最大公約數(shù)(gcd)
    //原理：輾轉(zhuǎn)相除法，m%n==0則n就是最大公約數(shù)，否則gcd(m,n)等價(jià)于gcd(n,m%n)
    static int gcd(int m,int n) {
        if(n==0)
            return m;
        return gcd(n, m%n);
    }
}