理論上，任何循環(huán)都可以重寫為遞歸形式。
有些語言沒有循環(huán)語句，只能使用遞歸。

循環(huán)改遞歸

• 改為遞歸的關(guān)鍵是發(fā)現(xiàn)邏輯“相似性”。
• 不要忘記遞歸“出口”。

例1：打印從1到n的整數(shù)。

下面的代碼是通過for循環(huán)實(shí)現(xiàn)：

public class 遞歸1_循環(huán) {
    public static void main(String[] args){
        for(int i=0;i<10;i++){
            System.out.println(i);
        }
    }
}

如果用遞歸，可以有以下思路：
我負(fù)責(zé)打印最后一個(gè)，但是我前面的人負(fù)責(zé)打印0-n-1個(gè)
由這個(gè)思路，通過這樣的代碼來實(shí)現(xiàn)：

public class 遞歸1_循環(huán) {
    public static void main(String[] args){
        f(9);
    }
    public static void f(int n){
        if(n>=0){
            f(n-1);
            System.out.print(n+" ");
        }
    }
}

所以，我們可以拓展成這樣：

public class 遞歸1_循環(huán) {
    public static void main(String[] args) {
        f(0, 9);
    }
    public static void f(int begin, int end) {
        if (begin > end) {
            return;
        }
        System.out.print(begin+" ");
        f(begin + 1, end);
    }
}

構(gòu)造相似性

• 如果沒有明顯的相似性，需要主動(dòng)構(gòu)造。
• 不能相似的原因很可能是缺少參數(shù)。
• 遞歸與數(shù)學(xué)上的遞推公式很類似。

例2：數(shù)組求和

可通過for循環(huán)來實(shí)現(xiàn)這個(gè)需求：

public class 遞歸2_求和 {
    public static void main(String[] args){
        int []a={1,2,3,4,5,6,7,8,9,10};
        System.out.println(f(a));
    }
    public static int f(int []a){
        int x=0;
        for (int i=0;i<a.length;i++){
            x+=a[i];
        }
        return x;
    }
}

通過遞歸實(shí)現(xiàn)：
如果用遞歸實(shí)驗(yàn)，目前有三種思路：

1. a[begin]+(begin+1......結(jié)束)。
2. (a[0]...end-1)+a[end]。
3. 折半求和 mid=(begin+end)/2,[begin,mid)[mid,end)。

下面是第一個(gè)思路：

public class 遞歸2_求和 {
    public static void main(String[] args){
        int []a={1,2,3,4,5,6,7,8,9,10};
        System.out.println(f(a,0));
    }
    public static int f(int []a,int begin){
        if(a.length==0)
            return 0;
        if(a.length<=begin){
            return 0;
        }
        return a[begin]+f(a,begin+1);
    }
}

慢慢地發(fā)現(xiàn)，遞歸就是一個(gè)踢皮球的游戲。

例3：字符串匹配

用equals函數(shù)來實(shí)現(xiàn)：

import java.util.Arrays;
public class 遞歸3_字符串匹配 {
    public static void main(String[] args){
        String a="abc";
        String b="abc";
        System.out.println(f(a,b));
    }
    public static boolean f(String a,String b){
        return a.equals(b);
    }
}

用遞歸來實(shí)現(xiàn)：

import java.util.Arrays;
public class 遞歸3_字符串匹配 {
    public static void main(String[] args){
        String a="abc";
        String b="abc";
        System.out.println(f(a,b));
    }
    public static boolean f(String a,String b){
        if(a.length()!=b.length()){
            return  false;
        }
        if(a.length()==0){
            return true;
        }
        if(a.charAt(0)!=b.charAt(0)){
            return false;
        }else{
            return f(a.substring(1),b.substring(1));
        }
    }
}

例4：求階乘

public class Factorial {
    public static int fact(int n) {
        int result;
        if(n==1||n==0) {
            result=1;
        }else {
            result=n*fact(n-1);
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println(fact(5));
    }
}

遞歸調(diào)用

• 遞歸調(diào)用僅僅是被調(diào)函數(shù)恰為主調(diào)函數(shù)
• 注意每次調(diào)用的層次不同
• 注意每次分配形參并非同一個(gè)變量
• 注意返回的次序

現(xiàn)實(shí)中的“遞歸”

遞歸思想：
我做最后一個(gè)/我做第一個(gè)，你告訴我誰是最后一個(gè)（加參）
然后其他的交給長得跟我一樣的下屬。（相似性）
并且要求你到什么時(shí)候就不能往下交了（設(shè)置出口）

遞歸類型：有返回&沒返回
沒返回：老板做（【需要加參】或尾），然后推給下屬，并限定到哪
有返回：老板最后返回總的情況，推給下屬，限定到哪，底層下屬返回一個(gè)

使用遞歸的步驟

• 找重復(fù)

1. 找到一種劃分方法
2. 找到遞推公式或者等價(jià)轉(zhuǎn)換（都是父問題轉(zhuǎn)換為求解子問題）

• 找變化的量
  變化的量通常要作為參數(shù)
• 找到出口
  根據(jù)參數(shù)變化的趨勢，對(duì)邊界進(jìn)行控制，適時(shí)終止遞歸