递归与循环

理论上，任何循环都可以重写为递归形式。
有些语言没有循环语句，只能使用递归。

循环改递归

• 改为递归的关键是发现逻辑“相似性”。
• 不要忘记递归“出口”。

例1：打印从1到n的整数。

下面的代码是通过for循环实现：

public class 递归1_循环 {
    public static void main(String[] args){
        for(int i=0;i<10;i++){
            System.out.println(i);
        }
    }
}

如果用递归，可以有以下思路：
我负责打印最后一个，但是我前面的人负责打印0-n-1个
由这个思路，通过这样的代码来实现：

public class 递归1_循环 {
    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_循环 {
    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);
    }
}

构造相似性

• 如果没有明显的相似性，需要主动构造。
• 不能相似的原因很可能是缺少参数。
• 递归与数学上的递推公式很类似。

例2：数组求和

可通过for循环来实现这个需求：

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;
    }
}

通过递归实现：
如果用递归实验，目前有三种思路：

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

下面是第一个思路：

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);
    }
}

慢慢地发现，递归就是一个踢皮球的游戏。

例3：字符串匹配

用equals函数来实现：

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);
    }
}

用递归来实现：

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));
    }
}

递归调用

• 递归调用仅仅是被调函数恰为主调函数
• 注意每次调用的层次不同
• 注意每次分配形参并非同一个变量
• 注意返回的次序

现实中的“递归”

递归思想：
我做最后一个/我做第一个，你告诉我谁是最后一个（加参）
然后其他的交给长得跟我一样的下属。（相似性）
并且要求你到什么时候就不能往下交了（设置出口）

递归类型：有返回&没返回
没返回：老板做（【需要加参】或尾），然后推给下属，并限定到哪
有返回：老板最后返回总的情况，推给下属，限定到哪，底层下属返回一个

使用递归的步骤

• 找重复

1. 找到一种划分方法
2. 找到递推公式或者等价转换（都是父问题转换为求解子问题）

• 找变化的量
  变化的量通常要作为参数
• 找到出口
  根据参数变化的趋势，对边界进行控制，适时终止递归