递归与循环

一.递归与循环

递归，说白了就是自己调用自己。理论上，任何的循环都可以重写为递归形式，所有的递归也可以被表述成循环的形式，本文主要介绍如何将循环重写为递归。

二.循环改递归的两大要点

发现逻辑“相似性”
不要忘记递归的“出口”

小例子：

public class demo{
    public static void main(String[] args){
        for(int i=0;i<10;i++){
            System.out.println(i);
        }
    }
}

上述代码的输出结果是打印出数字“0-9”。

这是利用循环实现，接下来我们将循环改写为递归：

public class Main{
    public static void f(int n){
        if(n<0) return;//出口
        f(n-1);//打印0 ~ n-1
        System.out.println(n);//打印n
    }
    public static void main(String[] args){
       f(9);
    }
}

思路解释：“踢皮球”-常用来形容政府职能部门职责不清，相互推诿，比如你要到部门A盖个章，A叫你先去部门B盖章，B叫你去部门C盖章...这种将工作以踢皮球的方式甩给其他人做的方式其实很适用于递归。

但在递归中，如果你甩给其他人的工作和分配给你的工作完全一样，则程序陷入死循环，一直没有人进行工作，一直在甩锅，因此，递归中为：自己做一小部分事情，剩下的事情再甩给其他人去做。

我们要做的是打印除数字“0 - 9”，那么，我完全可以自己负责打印其中一个数（代码中表现为打印末尾数字9），将剩下的数字“0 - 8”交予其他人去打印，比如A打印9，B负责打印“0-8”，B又打印8,并将“0-7”甩给C去负责，C又打印7，剩下的甩给D......

每次甩给下个人的工作都少了一点，在代码中表现为每次进行调用的参数都不一致，这就是发现逻辑“相似性”，每次调用的都是f(int n)这个方法，但每次参数都发生了变化，即f(n-1)。

但若一直递归下去，程序将陷入死循环，当n=0时，又会调用f(-1)，这显然不正确，因此，我们需要给递归加上一个出口限制，即if(n<0) return;，当n<0时，代表0~9都已经打印完毕，我们需要终止递归。

注：并不一定非得A打印9，将“0~8” 甩给B...也可以A负责打印首位0，将“1~9”甩给B...这种情况有些许不一样（其实就是参数发生了变化）,代码如下：

public static void f2(int begin,int end){
    if(begin>end) return;
    System.out.println(begin);
    f2(begin+1,end);
}

由上可看出，循环转递归，可能并非只有一种解法，也可存在多种改写形式，但都遵循“相似性”+“出口”的原则。

三.构造相似性

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

在循环转递归的过程中，可能并不具有非常明显的相似性，很可能是因为缺少参数的原因，这时候就需要我们去主动构造相似性，通常为增加参数来实现。

例子1：

public class demo{
    public static int addAll(int[] a){
        int x=0;
        for(int i=0;i<a.length;i++){
            x+=a[i];
        }
        return x;
    }
    public static void main(String[] args){
        int[] a={3,4,11,8};
        int sum=addAll(a);
        System.out.println(sum);
    }
}

上述代码的功能为将数组a中的所有元素求和并打印。接下来，将循环改写为递归：

public class Main{
    public static int f(int[] a,int begin){
        if(begin==a.length) return 0;//出口
        int x=f(a,begin+1);
        return x+a[begin];
    }
    public static void main(String[] args){
        int[] a={3,4,11,8};
        int sum=f(a,0);
        System.out.println(sum);
    }
}

转为递归求和，我们一开始想到的肯定是定义一个求和方法，方法内传入要求和的数组，即 f(int[] a) ,但这样踢皮球每次甩给别人的都是原封不动的任务，导致程序进入死循环，因此我们需要加入一个参数 int begin 作为当前对象负责求和的起始元素的下标，这样，A只需要将 begin+1~end 的求和工作甩给B去做，B只需要再将拿到的begin进行+1操作,然后甩给C去做......待B传回求和的值，A再将B传回的值加上a[0]就可以得到数组所有元素之和了。

注：除了上述解法之外，还有以下解法：

[0......end-1]　［end］，将数组拆成两部分，A负责end，将0~end-1甩给B去做；

折半求和：

public class Main{
    public static int f(int[] a,int begin,int end){
     if(begin>end) return 0;
     int middle = (begin+end)/2; //取中值
     if(begin==end){
         return a[end];
     }
     return f(a,begin,middle)+f(a,middle+1,end);     
    }

    public static void main(String[] args){
        int[] a={3,4,11,8};
        int sum=f(a,0,a.length-1);
        System.out.println(sum);
    }
}

例子2：

public class demo{
    public static boolean isSameString(String s1,String s2){
        return s1.equals(s2);
    }
    public static void main(String[] args){
        System.out.println(isSameString("abc","abcd"));
    }
}

上述代码的功能为比较两个字符串是否相同。接下来，将循环改写为递归：

public class Main {
    public static boolean f(String s1, String s2) {
        if(s1.length()!=s2.length()) {
            return false;
        }
        if(s1.length()==0) {//出口：当比较至两字符串为空时表示两字符串各字符均相同
            return true;
        }
        if(s1.charAt(0)!=s2.charAt(0)) {
            return false;
        }
        return f(s1.substring(1),s2.substring(1));
    }
    public static void main(String[] args) {
        System.out.println(f("abc", "abcd"));
    }
}

四.递归调用

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

image

如图所示：A运行到节点a，调用B，B运行到节点b，调用C，C执行结束之后，将结果返回节点b，B从节点b开始继续运行，B执行结束之后将结果返回节点a，A再从节点a开始继续运行...

该执行过程要求每一次节点中断调用其他方法，必须记录下该中断节点的环境信息，作用是为了调用结束返回结果之后原程序能够从上次中断位置起继续执行，在计算机中，通过一个栈结构来实现该效果(栈:先进后出)：

A执行至a时将要去调用B，此时将节点a的环境信息通过压栈的方式保存在栈结构中，同理，在b节点处又将节点b的环境信息通过压栈的方式保存在栈结构中；

当C执行结束返回结果给B时，通过弹栈的方式将b进行出栈操作，这样B就可以从b开始继续运行，同理，当B执行完毕返回结果给A时，通过弹栈的方式将a进行出栈操作，这样A就可以从a开始继续运行。

逐层深入，逐层返回。