递归（Recursion）

递归（Recursion）

• 递归：函数（方法）直接或间接调用自身。是一种常用的编程技巧
• 生活中的案例：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？【从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？『从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什呢？……』

（1）函数的调用过程

public static void main(String[] args){
	test1(10);
	test2(20);
}
private static void test1(int v){}

private static void test2(int v){
	test3(30);
}
private static void test3(int v){}
1
2
3
4
5
6
7
8
9
10

（2）函数的递归调用过程

public static void main(String[] args){
	sum(4);
}
private static int sum(int n){
	if(n <= 1) return n;
	return n + sum(n-1);
}
1
2
3
4
5
6
7

• 如果递归调用没有终止，将会一直消耗栈空间
  最终导致栈内存溢出（Stack Overflow）
• 所以必需要有一个明确的结束递归的条件
  也叫作边界条件、递归基
  

（3）递归的基本思想

• 拆解问题
  把规模大的问题变成规模较小的同类型问题
  规模较小的问题又不断变成规模更小的问题
  规模小到一定程度可以直接得出它的解
• 求解
  由最小规模问题的解得出较大规模问题的解
  由较大规模问题的解不断得出规模更大问题的解
  最后得出原来问题的解
• 凡是可以利用上述思想解决问题的，都可以尝试使用递归
  很多链表、二叉树相关的问题都可以使用递归来解决
  ✓ 因为链表、二叉树本身就是递归的结构（链表中包含链表，二叉树中包含二叉树）

（4）递归的使用套路

• ① 明确函数的功能
  先不要去思考里面代码怎么写，首先搞清楚这个函数的干嘛用的，能完成什么功能？
• ② 明确原问题与子问题的关系
  寻找 f(n) 与 f(n – 1) 的关系
• ③ 明确递归基（边界条件）
  递归的过程中，子问题的规模在不断减小，当小到一定程度时可以直接得出它的解
  寻找递归基，相当于是思考：问题规模小到什么程度可以直接得出解？

（5）练习1 — 斐波那契数列

• 斐波那契数列：1、1、2、3、5、8、13、21、34、……
• F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n≥3）
• 编写一个函数求第 n 项斐波那契数

int fib(int n){
	if(n <= 2) return 1;
	return fib(n - 1) + fib(n - 2);
}
1
2
3
4

• 根据递推式 T(n) = T(n − 1)+ T(n − 2) + O(1)，可得知时间复杂度：O(2ⁿ）
• 空间复杂度：O(n)
  递归调用的空间复杂度 = 递归深度 * 每次调用所需的辅助空间

1、fib函数的调用过程

• 出现了特别多的重复计算
• 这是一种“自顶向下”的调用过程

2、fib优化1 — 记忆化

• 用数组存放计算过的结果，避免重复计算

public class Fib {
    public static void main(String[] args) {
        Fib fib = new Fib();
        System.out.println(fib.fib1(10));
    }

    int fib1(int n){
        if (n <= 2) return 1;
        int[] array = new int[n + 1];
        array[1] = array[2] = 1;
        return fib1(n,array);
    }
    int fib1(int n,int[] array){
        if (array[n] == 0){
            array[n] = fib1(n-1,array) + fib1(n-2,array);
        }
        return array[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 时间复杂度：O(n)，空间复杂度：O(n)
  

3、fib优化2

• 去除递归调用

int fib(int n){
	if(n <= 2) return 1;
	int[] array = new int[n+1];
	array[2] = array[1] = 1;
	for(int i = 3;i <= n; i++){
		array[i] = array[i-1] + array[i-2];
	}
	return array[n];
}
1
2
3
4
5
6
7
8
9

• 时间复杂度：O(n)，空间复杂度：O(n)
• 这是一种“自底向上”的计算过程

4、fib优化3

• 由于每次运算只需要用到数组中的 2 个元素，所以可以使用滚动数组来优化

int fib3(int n){
   if (n <= 2) return 1;
    int[] array = new int[2];
    array[0] = array[1] = 1;
    for (int i = 3; i <= n; i++) {
        array[i % 2] = array[(i-1) % 2]+array[(i-2) % 2];

    }
    return array[n % 2];
}
1
2
3
4
5
6
7
8
9
10

5、fib优化4 – 位运算取代模运算

/**
 * 4 % 2 = 0   0b100  & 0b001 = 0
 * 3 % 2 = 1   0b011  & 0b001 = 1
 * 5 % 2 = 1   0b101  & 0b001 = 1
 * 6 % 2 = 0   0b110  & 0b001 = 0
 */
int fib4(int n){
    if (n <= 2) return 1;
    int[] array = new int[2];
    array[0] = array[1] = 1;
    for (int i = 3; i <= n; i++) {
        array[i & 1] = array[(i-1) & 1]+array[(i-2) & 1];

    }
    return array[n & 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6、fib优化5

int fib5(int n){
    if (n <= 2) return 1;
    int first = 1;
    int second = 1;
    for (int i = 3; i <= n; i++) {
        second = first + second;
        first = second - first;
    }
    return second;
}
1
2
3
4
5
6
7
8
9
10

• 时间复杂度：O(n)，空间复杂度：O(1)

（5）练习2 — 上楼梯（跳台阶）

• 楼梯有 n 阶台阶，上楼可以一步上 1 阶，也可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法？
• 假设 n 阶台阶有 f(n) 种走法，第 1 步有 2 种走法
  ✓ 如果上 1 阶，那就还剩 n – 1 阶，共 f(n – 1) 种走法
  ✓ 如果上 2 阶，那就还剩 n – 2 阶，共 f(n – 2) 种走法
• 所以 f(n) = f(n – 1) + f(n – 2)
  

int climbStairs(int n){
    if ( n <= 2) return n;
    return climbStairs(n-1)+climbStairs(n-2);
}
1
2
3
4

• 跟斐波那契数列几乎一样，因此优化思路也是一致的

int climbStairs(int n){
	if(n <= 2) return n;
	int first = 1;
	int second = 2;
	for(int i=3; i<= n; i++){
		second = first+second;
		first = second - first;
	}
	return seconnd;
}
1
2
3
4
5
6
7
8
9
10

（6）递归转非递归

• 递归调用的过程中，会将每一次调用的参数、局部变量都保存在了对应的栈帧（Stack Frame）中

public class Main {

    static void log(int n){
        if (n < 1) return;
        log(n -1);
        int v = n+10;
        System.out.println(v);
    }

    public static void main(String[] args) {
        log(4);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 若递归调用深度较大，会占用比较多的栈空间，甚至会导致栈溢出
• 在有些时候，递归会存在大量的重复计算，性能非常差
  这时可以考虑将递归转为非递归（递归100%可以转换成非递归）
• 递归转非递归的万能方法
  ①、自己维护一个栈，来保存参数、局部变量。
  ②、但是空间复杂度依然没有得到优化。

import java.util.Stack;
public class Main {
    static class Frame{
        int n;
        int v;
        Frame(int n,int v){
            this.n=n;
            this.v=v;
        }
    }
    static void log1(int n){
        Stack<Frame> frames = new Stack<>();
        while (n > 0){
            frames.push(new Frame(n,n+10));
            n--;
        }
        while (!frames.isEmpty()){
            Frame frame = frames.pop();
            System.out.println(frame.v);
        }
    }

    public static void main(String[] args) {
        System.out.println("----");
        log1(4);
    }
}
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

（7）尾调用（Tail Call）

• 尾调用：一个函数的最后一个动作是调用函数
• 如果最后一个动作是调用自身，称为尾递归（Tail Recursion），是尾调用的特殊情况

/*尾调用*/
void test1(){
	int a = 10;
	int b = a +20;
	test2(b);
}
1
2
3
4
5
6

/*尾递归*/
void test2(){
	if(n < 10) return;
	test2(n-1);
}
1
2
3
4
5

• 一些编译器能对尾调用进行优化，以达到节省栈空间的目的
• 下面代码不是尾调用

int factorial(int n){
	if(n <= 1) return n;
	return n * factorial(n-1);//最后一个动作是乘法，
}
1
2
3
4

1.尾调用优化（Tail Call Optimization）

• 尾调用优化也叫做尾调用消除（Tail Call Elimination）
  ①、如果当前栈帧上的局部变量等内容都不需要用了，当前栈帧经过适当的改变后可以直接当作被尾调用的函数的栈帧
  使用，然后程序可以 jump 到被尾调用的函数代码
  ②、生成栈帧改变代码与 jump 的过程称作尾调用消除或尾调用优化
  ③、尾调用优化让位于尾位置的函数调用跟goto语句性能一样高
• 消除尾递归里的尾调用比消除一般的尾调用容易很多
  ①、比如Java虚拟机（JVM）会消除尾递归里的尾调用，但不会消除一般的尾调用（因为改变不了栈帧）
  ②、因此尾递归优化相对比较普遍，平时的递归代码可以考虑尽量使用尾递归的形式

2.尾递归示例1 —— 阶乘

• 求 n 的阶乘 123*…*(n-1)*n （n>0）

int factorical(int n){
	return factorical(n,1);
}
//result 从大到小累乘的结果
int factorical(int n,int result){
	if(n <= 1) return result;
	return factorical(n-1,n*result);
}
1
2
3
4
5
6
7
8

2.尾递归示例2 —— 斐波那契数列

int fib(int n){
	return fib(n,1,1);
}
public int fib(int n,int first,int second){
	if(n <= 1) return first;
	return fib(n-1,second,first+second);
}
1
2
3
4
5
6
7