定义

  • 计算机科学中，递归是一种解决计算问题的方法，其中解决方法取决于同一类问题的更小子集

比如单链表递归遍历的例子：

1
2
3
4
5
6
void f(Node node) {
    if(node == null){
        return;
    }
    f(node.next);
}

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

解题思路

1、确定能否使用递归求解
2、推导出递推关系，即父问题与子问题的关系，以及递归的结束条件

深入到最里层叫做递 从最里层出来叫做归
*在递的过程中，外层函数内的局部变量(以及方法参数)并未消失，归的时候还可以用到

例一- 阶乘

用递归方法求阶乘
·阶乘的定义 n！ = 1·2·3···(n-2)·(n-1)·n，其中n为自然数，当然0！ = 1
·递推关系:
f(n) = {
1，n=1
n * f(n-1) ,n>1
}

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 递归实现阶乘
 */
public class Factorial {
    public static int f(int n){
        if(n == 1){
            return 1;
        }
        return n * f(n-1);
    }

    public static void main(String[] args) {
        int f = f(5);
        System.out.println(f);
    }
}

例二- 反向打印字符串

使用递归反向打印字符串，n为字符在整个字符串str中的索引位置
·递：n从0开始，每次n+1，一直递到n == str.length() - 1
·归：从n == str.length() 开始归，自然是逆序的
递推关系：
f(n) = {
停止 n = str.length()
f(n+1) 0 ≤ n ≤ str.lenth() - 1
}

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 递归反向打印字符串
 */
public class ReversePrintString {
    public static void f(int n, String str){
        if (n == str.length()){
            return;
        }
        //要放在调用递归方法的后面才能实现逆序
        f(n + 1, str);
        System.out.println(str.charAt(n));
    }

    public static void main(String[] args) {
        f(0,"abcd");
    }
}

例三- 递归实现二分查找

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class E03BinarySearch {

    public static int search(int[] a, int target){

        //边界值包含的情况
        return f(a,target,0,a.length -1);
    }

    /**
     * 递归(子问题)函数
     * @param a-数组
     * @param target-待查找值
     * @param i-起始索引(包含)
     * @param j-结束索引(包含)
     * @return
     *      -找到返回索引
     *      -没找到返回-1
     */
    private static int f(int[] a,int target, int i, int j){
        //跳出递归的条件
        if(i > j){
            return -1;
        }
        int m = (i + j) >>> 1;
        if(target < a[m]){
            return f(a, target, i, m-1);
        }else if(a[m] < target){
            return f(a, target, i+1, j);
        }else {
            return m;
        }
    }
}

例四- 递归实现冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * 递归冒泡排序
 * -将数组划分成两部分[0..j][j+1 .. a.length-1]
 * -左边[0..j]是未排序部分
 * -右边[j+1 .. a.length-1]是已排序的部分
 * -未排序区间内，相邻的两个元素比较，如果前一个大于后一个，则交换位置
 */
public class E04BubbleSort {

    public static void sort(int[] a){
        bubble1(a,a.length -1 );
    }

    //j代表未排序区域右边界
    private static void bubble1(int[] a,int j){
        if(j == 0){
            return;
        }
        for (int i = 0; i < j; i++) {
            if(a[i] > a[i + 1]) {
                int t = a[i];
                a[i] = a[i+1];
                a[i+1] = t;
            }
        }
        //递归调用
        bubble1(a,j - 1);
    }

    /**
     * 递归函数(优化) 在范围[0 .. j]内冒泡最大元素到右侧
     * @param a-数组
     * @param j-未排序区域右边界
     */
    private static void bubble2(int[] a,int j){
        if(j == 0){
            return;
        }
        int x = 0;
        for (int i = 0; i < j; i++) {
            if(a[i] > a[i + 1]) {
                int t = a[i];
                a[i] = a[i+1];
                a[i+1] = t;
                //将i赋值给x会减少很多不必要的递归
                x = i;
            }
        }
        //递归调用
        bubble2(a,x);
    }
}

例五- 递归实现插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class E05InsertionSort {

    public static void sort(int[] a) {
        insertion(a, 1);
    }
    /**
     * 递归实现插入排序
     * @param a-数组
     * @param low-未排序区域的左边界
     */
    private static void insertion(int[] a, int low) {
        if (low == a.length) {
            return;
        }
        int t = a[low];
        int i = low - 1; // 已排序区域指针

        //找比t小的元素
        while(i >= 0 && a[i] > t) { //退出循环意味着找到了插入位置
            a[i+1] = a[i]; // 空出插入位置
            i--;
        }

        //找到插入位置
        if(i+1 != low){
            //减少一次赋值动作
            a[i+1] = t;
        }
        
        insertion(a, low + 1);
    }

        //另一种冒泡排序实现,但是赋值次数比上一次多得多,效率低
    private static void insertion2(int[] a,int low) {
        if(low == a.length) {
            return;
        }

        int i = low - 1;
        while(i >= 0 && a[i] > a[i+1]){
            int t = a[i];
            a[i] = a[i+1];
            a[i+1] = t;

            i--;
        }

        insertion2(a,low+1);
    }
}

例六- 斐波那契数列

·之前的例子是每个递归函数只包含一个自身的调用，这称之为 single recursion
·如果每个递归函数包含多个自身调用，称之为 multi recursion(多路递归)
递推关系：
f(n) = {
0, n=0
1, n=1
f(n-1) + f(n-2) n>1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 递归求斐波那契数列
 */
public class E06Fibonacci {

    // f(3) => 调用了5次递归
    // f(4) => 调用了9次递归
    // f(5) => 调用了15次递归
    // f(n) => 调用了 2*f(n+1) - 1次递归
    public static int f(int n){
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int x = f(n - 1);
        int y = f(n - 2);
        return x + y;
    }
}
  • 递归的次数也符合斐波那契数列，2*f(n+1) - 1
  • 它的时间复杂度为 O(1.618^n)

递归优化(动态规划)

空间换时间，数组存储递归值减少计算量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 使用Memoization(记忆法，也称备忘录)改进,空间换时间
 * @param n-第n项
 * @return 第n项的值
 */
public static int fibonacci(int n){
    //存储递归的值
    int[] cache = new int[n + 1];
    //初始化
    Arrays.fill(cache,-1); //[-1, -1, -1, -1]
    //赋值已知值
    cache[0] = 0;
    cache[1] = 1;//[0, 1, -1, -1]
    return f(n, cache);
}

public static int f(int n, int[] cache){
    if(cache[n] != -1){
        return cache[n];
    }
    int x = f(n - 1, cache);
    int y = f(n - 2, cache);
    cache[n] = x + y;//[0, 1, ?, -1] 存入数组
    return cache[n];
}

解决爆栈

尾调用

如果函数的最后一步是调用一个函数，那么称为尾调用，例如

1
2
3
4
5
6
7
8
9
10
11
12
13
funtion a(){
    return b();
}    
    //下面实例都不叫尾调用：
        //最后一步并非调用函数
        const c = b();
        return c;
        
        //最后一步虽然调用了函数，但是又用到了外层函数的数值1，相当于最后一步是加法操作
        return b() + 1;

        //下面同理使用了外层函数的变量x
        return b() + x;

尾调用的好处就是可以把嵌套的函数关系变成平级的函数关系，外层的函数不需要占着内存等内函数执行完就会被释放掉。
优雅！！！

1
2
3
4
5
6
funtion a(){
    return b();
} 
funtion b(){
    return 10000;
}

*散了吧，java编译器没优化递归的尾调用/(ㄒoㄒ)/~~

改成循环

返璞归真，还得是直接暴力循环，反正也比爆栈的报错强吧？哈哈哈

递归时间复杂度计算

主定理计算方法

若有递归式：
T(n) = aT(n/b) + f(n)
其中：

  • T(n)是问题的运行时间，n是数据规模
  • a是子问题的个数
  • T(n/b)是子问题的运行时间，每个子问题被拆成原问题数据规模的n/b
  • f(n)是除递归外执行的计算 令x = log[b]a,即x = log[子问题缩小倍数]子问题个数
    那么可得时间复杂度为：
    T(n) =
    {
    O(n^x) f(n) = O(n^c)并且c < x
    O(n^x * log[n]) f(n) = O(n^x)并且c = x
    O(n^c) f(n) = O(n^x)并且c > x
    }

例如：
1、T(n) 2T(n/2) + n^4 (此时a = 2,b = 2,x = log[b]a =1, c = 4再用上面的公式求解时间复杂度)
·此时x = 1 < 4,由后者决定整个时间复杂度O(n^4)

展开求时间复杂度

像T(n) = T(n - 1) + T(1) + n这种找不到abc的就不能用上面的办法，得使用数学方式展开求时间复杂度，类似于数列的递推公式

例如求：递归快排的时间复杂度
快速排序分区没分好的极端情况
T(n) = T(n - 1) + T(1) + n, T(1) = c
即:T(n) = T(n - 1) + c + n
下面为展开过程
T(n) = T(n - 2) + c + (n - 1) + c +n
T(n) = T(n - 3) + c + (n - 2) + (n - 1) + c +n
…
T(n) = T(n-(n-1)) + (n - 1)c + 2+...+n = n^2/2 + 2cn+n/2 - 1
时间复杂度为O(n^2)

不会推导的可以进入外挂 https://www.wolframalpha.com/
·例一：输入f(n) = f(n-1) + c,f(1) = c

汉诺塔

Tower of Hanol，是一个源于印度的古老传说：大梵天创建世界时做了三根金刚石柱，在一根柱子从下往上按大小顺序摞着64片黄金圆盘，大梵天命令婆罗门把圆盘重新摆放在另一根柱子上，并且规定

  • 一次只能移动一次圆盘
  • 小圆盘上不能放大圆盘

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class E02HanoiTower {
    //三个集合代表三个柱子
    static LinkedList<Integer> a =new LinkedList<>();
    static LinkedList<Integer> b =new LinkedList<>();
    static LinkedList<Integer> c =new LinkedList<>();

    /**
     * 初始化方法，将初始数量的圆盘放到a柱子上由大到小表示如[3, 2, 1]
     * @param n-圆盘数量
     */
    static void init(int n){
        for (int i = n; i >= 1 ; i--) {
            a.addLast(i);
        }
    }

    /**
     * @param n-圆盘个数
     * @param a-原始柱
     * @param b-借用柱
     * @param c-目标柱
     */
    static void move(int n, LinkedList<Integer> a,
                     LinkedList<Integer> b,
                     LinkedList<Integer> c) {
        if(n == 0){
            return;
        }
        //将上一步的一堆看作一个整体移到b上，比如321，拿出21移到b上，而且必须借助“借用柱”，这里的借用柱就是c
        move(n - 1, a, c, b);
        //剩下的最大的那一个圆盘直接移到目标柱，当然也要借用柱
        c.addLast(a.removeLast());
        print();
        //这时候再把那一堆放到目标c柱上即可，那一推会用递归变成我说的注释内容。妙！！！
        move(n - 1, b, a, c);
    }

    //查看柱子上的圆盘情况
    private static void print() {
        System.out.println("----------------------");
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }

    public static void main(String[] args) {
        init(3);
        print();
        move(3, a, b, c);
        print();
    }
}

时间复杂度估算
T(n) = 2T(n - 1) + c, T(1) = c
用展开求解
T(n) = c(2^n - 1)
即时间复杂度O(2^n)

杨辉三角

有三种方法：
第一种：直接递归
第二种：二维数组记忆法，也有递归
第三种：直接一维数组不需要递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public class E03PascalTriangle {

    /**
     * 直接递归
     * @param i-行坐标
     * @param j- 列坐标
     * @return 该坐标元素值
     */
    private static int element(int i, int j){
        if(j == 0 || i == j){
            return 1;
        }
        return element(i - 1,j - 1) + element(i - 1, j);
    }

    /**
     * 打印空格实现金字塔杨辉三角
     * @param n-阶数
     * @param i-每行
     */
    private static void printSpace(int n , int i) {
        int sum = (n - 1 - i) * 2;
        for (int j = 0; j < sum; j++) {
            System.out.print(" ");
        }
    }

    /**
     * 直角等腰三角形版杨辉三角
     * @param n-阶数
     */
    public static void print(int n) {
        for (int i = 0; i < n; i++) {
            printSpace(n , i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d",element(i, j));//-号表示左对齐，4d表示每次格式化空格单位
            }
            System.out.println();
        }
    }


    /**
     * 优化一-使用二维数组记忆法
     * @param i-行坐标
     * @param j-列坐标
     * @return 该坐标元素值
     */
    private static int element1(int[][] triangle, int i, int j){
        //因为数组默认值是0，只要计算过了那么就说明大于0直接返回
        if(triangle[i][j] > 0){
            return triangle[i][j];
        }
        if(j == 0 || i == j){
            triangle[i][j] = 1;
            return 1;
        }
        triangle[i][j] =  element1(triangle, i - 1,j - 1) + element1(triangle, i - 1, j);
        return triangle[i][j];
    }

    /**
     * 等腰三角形版杨辉三角(二位数组存储优化递归)
     * @param n-阶数
     */
    public static void print1(int n) {
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            triangle[i] = new int[i+1];//第i行列的个数就是i+1
            printSpace(n , i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d",element1(triangle, i, j));//-号表示左对齐，4d表示每次格式化空格单位
            }
            System.out.println();
        }
    }


    /**
     * <h3>优化2-使用一维数组记忆法</h3>
     * @param row-行数组
     * @param i-行号
     */
    /*
        0 0 0 0 0 0     初始状态
        1 0 0 0 0 0     i=0
        1 1 0 0 0 0     i=1
        1 2 1 0 0 0     i=2
        1 3 3 1 0 0     i=3
        1 4 6 4 1 0     i=4
     */
    private static void creatRow(int[] row, int i){
        if(i == 0){
            row[0] = 1;
            return;
        }
        for (int j = i; j > 0 ; j--) {
            row[j] = row[j] + row[j - 1];
        }
    }

    public static void print2(int n) {
        int[] row = new int[n];
        for (int i = 0; i < n; i++) {
            creatRow(row,i);
            printSpace(n , i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", row[j]);//-号表示左对齐，4d表示每次格式化空格单位
            }
            System.out.println();
        }
    }
}