遞迴

1 遞迴的構成

• 關係式
• 終止條件

遞迴的運作就在於，一個函式不斷地呼叫自己，直到達成終止條件才結束

終止條件就像是遞迴的心臟，一定要有終止條件才可以避免無窮呼叫的窘況

function Recur_fun(){
    if ( 終止條件 )
       return ...
    else
       return 呼叫自己
}

2 遞迴基本題 計算

2-1 計算1+4+9+....+n*n=?

//PURPOSE:用遞迴計算1+2+...+N=?
public static  void  main(String[] args) {

    Scanner s=new Scanner(System.in);
    int n=s.nextInt();
    System.out.println("1+4+...+"+(n*n)+"="+sum(n));

}
public static int sum(int n){ //static函數main一定要使用同為static的function
    if(n==1){//終止條件
        return 1;
    }else{
        return n*n+sum(n-1);
    }

}
------------------------------
4
1+4+...+16=30

sum(4)=4*4+sum(3) =16+14=30

sum(3)=3*3+sum(2) =9+5=14

sum(2)=2*2+sum(1) =5

sum(1)=1

2-2 計算n!=?

前面有試過用for迴圈來進行 n! 的計算，現在來試試看如何用遞迴撰寫來達到相同目的，寫完後記得與for迴圈寫法相比較

//PURPOSE:計算5!
public static void main(String[] args) {
    System.out.println(factorial(5));
}
public static int factorial(int n){
    if(n==1){
        return 1;
    }
    else{
        return n*factorial(n-1);
    }
}
--------------------
120

factorial(5)=5*factorial(4)

factorial(4)=4*factorial(3)

factorial(3)=3*factorial(2)

factorial(2)=2*factorial(1)

factorial(1)=1

2-3 求費式數列第n項的數為何

//PURPOSE:求費式數列第N項數為何
public static  void  main(String[] args) {

    Scanner s=new Scanner(System.in);
    int n=s.nextInt();
    System.out.println("費式數列的第"+n+"項="+fibonacci(n));

}
public static int fibonacci(int n){ //static函數main一定要使用同為static的function
    if(n<=2){//前兩項皆=1
        return 1;
    }else{//後面幾項=前一項+前二項
        return fibonacci(n-1)+fibonacci(n-2);
    }
}
-----------------
5
費式數列的第5項=5

fibonacci(5)=fibonacci(4)+fibonacci(3)

fibonacci(4)=fibonacci(3)+fibonacci(2)

fibonacci(3)=fibonacci(2)+fibonacci(1)

fibonacci(2)=1

fibonacci(1)=1

2-4 計算最大公因數與最小公倍數

//PURPOSE:找出兩數字的最大公因數與最小公倍數
public static void main(String[] args) {

    System.out.println("25及10的最大公因數="+GCD(25,10));
    System.out.println("25及10的最小公倍數="+LCM(25,10,GCD(25,10)));

}
public static int GCD(int x,int y){
 //輾轉相除法
    if(x%y==0){
        return y;
    }
    else{
        return GCD(y,x%y);
    }
}
public static int LCM(int x,int y,int gcd){ //最小公倍數=兩數相乘/最大公因數
    return x*y/gcd;
}
-----------------------------------------------
25及10的最大公因數=5
25及10的最小公倍數=50

進階題：用for或while迴圈找出最大公因數與最小公倍數

3 非遞迴 vs 遞迴