void f(Node node) {
    if(node == null) {
        return;
    }
    println("before:" + node.value)
    f(node.next);
    println("after:" + node.value)
}

说明：

自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的（有规律的）。
每次调用，函数处理的数据会较上次缩减（子集），而且最后会缩减至无需继续递归。
内层函数调用（子集处理）完成，外层函数才能算调用完成。

1.1.2原理

假设链表中有 3 个节点，value 分别为 1，2，3，以上代码的执行流程就类似于下面的伪码

// 1 -> 2 -> 3 -> null  f(1)
void f(Node node = 1) {
    println("before:" + node.value) // 1
    void f(Node node = 2) {
        println("before:" + node.value) // 2
        void f(Node node = 3) {
            println("before:" + node.value) // 3
            void f(Node node = null) {
                if(node == null) {
                    return;
                }
            }
            println("after:" + node.value) // 3
        }
        println("after:" + node.value) // 2
    }
    println("after:" + node.value) // 1
}

1.1.3思路

确定能否使用递归求解
推导出递推关系，即父问题与子问题的关系，以及递归的结束条件
深入到最里层叫做递
从最里层出来叫做归
在递的过程中，外层函数内的局部变量（以及方法参数）并未消失，归的时候还可以用到

1.2单路递归

1.2.1阶乘

用递归方法求阶乘

阶乘的定义 $n!= 1⋅2⋅3⋯(n-2)⋅(n-1)⋅n$，其中 n 为自然数，当然 0! = 1

编辑

代码实现：

private static int fac(int num) {
    if (num < 1) {
        return 1;
    }
    return num * f(num - 1);
}

拆解伪码如下，假设 n 初始值为 3:

f(int num = 3) { // 解决不了,递
    return 3 * f(int num = 2) { // 解决不了,继续递
        return 2 * f(int num = 1) {
            if (num < 1) { // 可以解决, 开始归
                return 1;
            }
        }
    }
}

1.2.2正向输出数字

public static void Print(int num){
        if(num>9){
            Print(num/10);
        }
        System.out.print(num%10);
    }

1.2.3反向输出字符串

用递归反向打印字符串，n 为字符在整个字符串 str 中的索引位置。

递：n 从 0 开始，每次 n + 1，一直递到 n == str.length() - 1
归：从 n == str.length() 开始归，从归打印，自然是逆序的编辑

public static void Print(String str,int index){
        if(index<str.length()-1){
            Print(str,index+1);
        }
        //System.out.println(str.substring(index,index+1));
        System.out.println(str.charAt(index));
    }

拆解伪码如下，假设字符串为 "abc"。

void reversePrint(String str, int index = 0) {
    void reversePrint(String str, int index = 1) {
        void reversePrint(String str, int index = 2) {
            void reversePrint(String str, int index = 3) { 
                if (index == str.length()) {
                    return; // 开始归
                }
            }
            System.out.println(str.charAt(index)); // 打印 c
        }
        System.out.println(str.charAt(index)); // 打印 b
    }
    System.out.println(str.charAt(index)); // 打印 a
}

1.3多路递归

1.3.1斐波那契数列

概念：如果每个递归函数例包含多个自身调用，称之为 multi recursion

编辑

public static int fib(int num) {
    if (num == 0) {
        return 0;
    }
    if (num == 1) {
        return 1;
    }
    return fib(num - 1) + fib(num - 2);
}

编辑

1.3.2兔子问题

编辑

第一个月，有一对未成熟的兔子（黑色，注意图中个头较小）
第二个月，它们成熟
第三个月，它们能产下一对新的小兔子（蓝色）
所有兔子遵循相同规律，求第 n 个月的兔子数

分析

兔子问题如何与斐波那契联系起来呢？设第 n 个月兔子数为 f(n)

f(n) = 上个月兔子数 + 新生的小兔子数

而【新生的小兔子数】实际就是【上个月成熟的兔子数】

因为需要一个月兔子就成熟，所以【上个月成熟的兔子数】也就是【上上个月的兔子数】

上个月兔子数，即 f(n-1)

上上个月的兔子数，即 f(n-2)

f(n)=f(n-1)+f(n-2);

因此本质还是斐波那契数列，只是从其第一项开始

1.3.3青蛙爬楼梯

楼梯有 n 阶
青蛙要爬到楼顶，可以一次跳一阶，也可以一次跳两阶
只能向上跳，问有多少种跳法

编辑

因此本质上还是斐波那契数列，只是从其第二项开始

对应 leetcode 题目 70. 爬楼梯 - 力扣（LeetCode）

1.4汉诺塔问题

该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

编辑

设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步：

(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；

(2)将A杆中剩下的第n号盘移至C杆；

(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。

递归法：

实际操作中，只有第二步可直接完成，而第一、三步又成为移动的新问题。以上操作的实质是把移动n个盘子的问题转化为移动n-1个盘，那一、三步如何解决？事实上，上述方法设盘子数为n, n可为任意数，该法同样适用于移动n-1个盘。因此，依据上法，可解决n -1个盘子从A杆移到B杆(第一步)或从B杆移到C杆(第三步)问题。现在，问题由移动n个盘子的操作转化为移动n-2个盘子的操作。依据该原理，层层递推，即可将原问题转化为解决移动n -2、n -3… … 3、2，直到移动1个盘的操作，而移动一个盘的操作是可以直接完成的。

//代码实现：
public static void Tower(int num,char A,char B,char C){
        //num表示盘子的个数，A,B,C表示A塔，B塔，C塔
        if(num==1){
            System.out.println("移动:"+A+"到"+C);
        }
        else{
            //如果有多个盘子，可以看成两个，最下面的，上面所有的盘子(num-1)
            //(1.)先移动上面所有的盘子到B盘，借助C盘
            Tower(num-1,A,C,B);
            //(2.)把最下面的盘移动到C盘
            System.out.println("移动:"+A+"到"+C);
            //(3.)再把B塔上的盘子移动到C盘，借助A盘
            Tower(num-1,B,A,C);
        }
    }

1.5猴子吃桃问题

猴子吃桃子问题: 有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个! 以后每天猴子都吃其中的一半，然后再多吃一个。当到第10天时，想再吃时(即还没吃)，发现只有1个桃子了。问题:最初共多少个桃子?

//代码实现
  //猴子吃桃问题
    //day10：1个桃子
    //day9:(day10+1)*2
    //day8:(day9+1)*2
public static int Peach(int day){
        if(day<0||day>10){
            return -1;
        }
        if(day==10){
            return 1;
        }
        else if(day>=1&&day<=9){
            return (Peach(day+1)+1)*2;
        }
        return -1;
    }

1.6老鼠走迷宫问题

目标：小球从1-1走到6-5

编辑

迷宫问题：

1.小球得到的路径，和程序员设置的找路策略有关：找路的上下左右的先后顺序

//代码实现
public static void main(String[] args) {
      //思路：
        //1.设置迷宫，通过二维数组表示int[][] map=new int[8][7];
      //2.规定：0表示可以走，1表示障碍物
        int[][] map=new int[8][7];//8行7列
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                //设置最上面一行和最下面一行为1
                map[0][j]=1;
                map[7][j]=1;
                if(i>=1&&i<7){
                    //设置最右面和最左面一列为1
                    map[i][0]=1;
                    map[i][6]=1;
                }
            }
        }
        //输出迷宫
        disPlay(map);
        //设置障碍物
        map[2][1]=1;
        map[2][2]=1;
        disPlay(map);
        //找路
        findWay(map,1,1);
        disPlay(map);
    }
    public static void disPlay(int[][] map){
        System.out.println("==============================");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static boolean findWay(int[][] map,int i,int j){
        //1.findWay方法找出迷宫的路径
        //2.如果找到，返回true，否则返回false
        //3.i,j表示老鼠的位置，初始化的位置为(1,1);
        //4.0表示可以走，1表示障碍物，2表示可以走，3表示走过但是走不通，是一条死路
        //5.当map[5][6]==2，说明找到了通路，此时就可以结束，否则继续找
        if(map[6][5]==2){//说明已经找到
            return true;
        }
        else{
            if(map[i][j]==0){ //表示当前位置可以走
                //假定该位置可以走通
                map[i][j]=2;
                //找路的逻辑：我的：右下左上（逻辑不通找路结果不同）或者【下右上左】
                if(findWay(map,i,j+1)){//右
                    return true;
                }
                else if(findWay(map,i+1,j)){//下
                    return true;
                }
                else if(findWay(map,i,j-1)){//左
                    return true;
                }
                else if(findWay(map,i-1,j)){//上
                    return true;
                }
                else{
                    map[i][j]=3;
                    return false;
                }
            }
            else{
                return false;
            }
        }
    }

2.存在回溯现象

//修改上述部分代码
        //设置障碍物
        map[3][1]=1;
        map[3][2]=1;
      map[2][2]=1;
        disPlay(map);

二、递归的时间复杂度

递归式：

其中

T(n) 是问题的运行时间，n 是数据规模
a 是子问题个数
T(\frac{n}{b}) 是子问题运行时间，每个子问题被拆成原问题数据规模的 \frac{n}{b}
f(n) 是除递归外执行的计算

教你精通Java语法之第十二章、递归

一、递归

1.1递归的概念

1.1.1定义