概述

定义

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

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

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

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

说明：

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

原理

假设链表中有 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. 确定能否使用递归求解
2. 推导出递推关系，即父问题与子问题的关系，以及递归的结束条件

例如之前遍历链表的递推关系为
$$f(n)=\{\begin{array}{ll}停止& n=null\\ f(n.next)& n\ne null\end{array}$$

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

单路递归 Single Recursion

E01. 阶乘

用递归方法求阶乘

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

• 递推关系

$$f(n)=\{\begin{array}{ll}1& n=1\\ n\ast f(n-1)& n>1\end{array}$$

代码

private static int f(int n) {
    if (n == 1) {
        return 1;
    }
    return n * f(n - 1);
}

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

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

E02. 反向打印字符串

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

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

递推关系
$$f(n)=\{\begin{array}{ll}停止& n=str.length()\\ f(n+1)& 0\le n\le str.length()-1\end{array}$$
代码为

public static void reversePrint(String str, int index) {
    if (index == str.length()) {
        return;
    }
    reversePrint(str, 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
}

多路递归 Multi Recursion

• 之前的例子是每个递归函数只包含一个自身的调用，这称之为 single recursion
• 如果每个递归函数例包含多个自身调用，称之为 multi recursion

E01. 斐波那契数列

递推关系
$$f(n)=\{\begin{array}{ll}0& n=0\\ 1& n=1\\ f(n-1)+f(n-2)& n>1\end{array}$$

下面的表格列出了数列的前几项

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13
0	1	1	2	3	5	8	13	21	34	55	89	144	233

实现

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

执行流程

• 绿色代表正在执行（对应递），灰色代表执行结束（对应归）
• 递不到头，不能归，对应着深度优先搜索

时间复杂度

• 递归的次数也符合斐波那契规律，$2\ast f(n+1)-1$
• 时间复杂度推导过程
  • 斐波那契通项公式 $f(n)=\frac{1}{\sqrt{5}}\ast ({\frac{1+\sqrt{5}}{2}}^n-{\frac{1-\sqrt{5}}{2}}^n)$
  • 简化为：$f(n)=\frac{1}{2.236}\ast ({1.618}^n-{(-0.618)}^n)$
  • 带入递归次数公式 $2\ast \frac{1}{2.236}\ast ({1.618}^{n+1}-{(-0.618)}^{n+1})-1$
  • 时间复杂度为 $\Theta (1.618^n)$

1. 更多 Fibonacci 参考[^8][9][^10]
2. 以上时间复杂度分析，未考虑大数相加的因素

变体1 - 兔子问题[^8]

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

分析

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

• $f(n)$ = 上个月兔子数 + 新生的小兔子数
• 而【新生的小兔子数】实际就是【上个月成熟的兔子数】
• 因为需要一个月兔子就成熟，所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
• 上个月兔子数，即 $f(n-1)$
• 上上个月的兔子数，即 $f(n-2)$

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

变体2 - 青蛙爬楼梯

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

分析

n	跳法	规律
1	(1)	暂时看不出
2	(1,1) (2)	暂时看不出
3	(1,1,1) (1,2) (2,1)	暂时看不出
4	(1,1,1,1) (1,2,1) (2,1,1) (1,1,2) (2,2)	最后一跳，跳一个台阶的，基于f(3) 最后一跳，跳两个台阶的，基于f(2)
5	…	…

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

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

递归优化-记忆法

上述代码存在很多重复的计算，例如求 $f(5)$ 递归分解过程

可以看到（颜色相同的是重复的）：

• $f(3)$ 重复了 2 次
• $f(2)$ 重复了 3 次
• $f(1)$ 重复了 5 次
• $f(0)$ 重复了 3 次

随着 $n$ 的增大，重复次数非常可观，如何优化呢？

Memoization 记忆法（也称备忘录）是一种优化技术，通过存储函数调用结果（通常比较昂贵），当再次出现相同的输入（子问题）时，就能实现加速效果，改进后的代码

public static void main(String[] args) {
    int n = 13;
    int[] cache = new int[n + 1];
    Arrays.fill(cache, -1);
    cache[0] = 0;
    cache[1] = 1;
    System.out.println(f(cache, n));
}

public static int f(int[] cache, int n) {
    if (cache[n] != -1) {
        return cache[n];
    }

    cache[n] = f(cache, n - 1) + f(cache, n - 2);
    return cache[n];
}

优化后的图示，只要结果被缓存，就不会执行其子问题

• 改进后的时间复杂度为 $O(n)$
• 请自行验证改进后的效果
• 请自行分析改进后的空间复杂度

注意

1. 记忆法是动态规划的一种情况，强调的是自顶向下的解决
2. 记忆法的本质是空间换时间

递归时间复杂度-Master theorem

若有递归式
$$T(n)=aT(\frac{n}{b})+f(n)$$
其中

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

令 $x={\log }_{b}a$，即 $x={\log }_{子问题缩小倍数}子问题个数$

那么
$$T(n)=\{\begin{array}{ll}\Theta (n^x)& f(n)=O(n^c)并且c<x\\ \Theta (n^x\log n)& f(n)=\Theta (n^x)\\ \Theta (n^c)& f(n)=\Omega (n^c)并且c>x\end{array}$$

例1

$T(n)=2T(\frac{n}{2})+n^4$

• 此时 $x=1<4$，由后者决定整个时间复杂度 $\Theta (n^4)$
• 如果觉得对数不好算，可以换为求【$b$ 的几次方能等于 $a$】

例2

$T(n)=T(\frac{7n}{10})+n$

• $a=1,b=\frac{10}{7},x=0,c=1$
• 此时 $x=0<1$，由后者决定整个时间复杂度 $\Theta (n)$

例3

$T(n)=16T(\frac{n}{4})+n^2$

• $a=16,b=4,x=2,c=2$
• 此时 $x=2=c$，时间复杂度 $\Theta (n^2\log n)$

例4

$T(n)=7T(\frac{n}{3})+n^2$

• $a=7,b=3,x=1.?,c=2$
• 此时 $x={\log }_{3}7<2$，由后者决定整个时间复杂度 $\Theta (n^2)$

例5

$T(n)=7T(\frac{n}{2})+n^2$

• $a=7,b=2,x=2.?,c=2$
• 此时 $x=lo{g}_{2}7>2$，由前者决定整个时间复杂度 $\Theta (n^{{\log }_{2}7})$

例6

$T(n)=2T(\frac{n}{4})+\sqrt{n}$

• $a=2,b=4,x=0.5,c=0.5$
• 此时 $x=0.5=c$，时间复杂度 $\Theta (\sqrt{n}\log n)$

例7. 二分查找递归

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, m + 1, j);
    } else {
        return m;
    }
}

• 子问题个数 $a=1$
• 子问题数据规模缩小倍数 $b=2$
• 除递归外执行的计算是常数级 $c=0$

$T(n)=T(\frac{n}{2})+n^0$

• 此时 $x=0=c$，时间复杂度 $\Theta (\log n)$

例8. 归并排序递归

void split(B[], i, j, A[])
{
    if (j - i <= 1)                    
        return;                                
    m = (i + j) / 2;             
    
    // 递归
    split(A, i, m, B);  
    split(A, m, j, B); 
    
    // 合并
    merge(B, i, m, j, A);
}

• 子问题个数 $a=2$
• 子问题数据规模缩小倍数 $b=2$
• 除递归外，主要时间花在合并上，它可以用 $f(n)=n$ 表示

$T(n)=2T(\frac{n}{2})+n$

• 此时 $x=1=c$，时间复杂度 $\Theta (n\log n)$

例9. 快速排序递归

algorithm quicksort(A, lo, hi) is 
  if lo >= hi || lo < 0 then 
    return
  
  // 分区
  p := partition(A, lo, hi) 
  
  // 递归
  quicksort(A, lo, p - 1) 
  quicksort(A, p + 1, hi) 

• 子问题个数 $a=2$
• 子问题数据规模缩小倍数
  • 如果分区分的好，$b=2$
  • 如果分区没分好，例如分区1 的数据是 0，分区 2 的数据是 $n-1$
• 除递归外，主要时间花在分区上，它可以用 $f(n)=n$ 表示

情况1 - 分区分的好

$T(n)=2T(\frac{n}{2})+n$

• 此时 $x=1=c$，时间复杂度 $\Theta (n\log n)$

情况2 - 分区没分好

$T(n)=T(n-1)+T(1)+n$

• 此时不能用主定理求解

递归时间复杂度-展开求解

像下面的递归式，都不能用主定理求解

例1 - 递归求和

long sum(long n) {
    if (n == 1) {
        return 1;
    }
    return n + sum(n - 1);
}

$T(n)=T(n-1)+c$，$T(1)=c$

下面为展开过程

$T(n)=T(n-2)+c+c$

$T(n)=T(n-3)+c+c+c$

…

$T(n)=T(n-(n-1))+(n-1)c$

• 其中 $T(n-(n-1))$ 即 $T(1)$
• 带入求得 $T(n)=c+(n-1)c=nc$

时间复杂度为 $O(n)$

例2 - 递归冒泡排序

void bubble(int[] a, int high) {
    if(0 == high) {
        return;
    }
    for (int i = 0; i < high; i++) {
        if (a[i] > a[i + 1]) {
            swap(a, i, i + 1);
        }
    }
    bubble(a, high - 1);
}

$T(n)=T(n-1)+n$，$T(1)=c$

下面为展开过程

$T(n)=T(n-2)+(n-1)+n$

$T(n)=T(n-3)+(n-2)+(n-1)+n$

…

$T(n)=T(1)+2+...+n=T(1)+(n-1)\frac{2+n}{2}=c+\frac{n^2}{2}+\frac{n}{2}-1$

时间复杂度 $O(n^2)$

注：

• 等差数列求和为 $个数\ast \frac{|首项-末项|}{2}$

例3 - 递归快排

快速排序分区没分好的极端情况

$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)+c+(n-1)+c+n$

…

$T(n)=T(n-(n-1))+(n-1)c+2+...+n=\frac{n^2}{2}+\frac{2cn+n}{2}-1$

时间复杂度 $O(n^2)$

不会推导的同学可以进入 https://www.wolframalpha.com/

• 例1 输入 f(n) = f(n - 1) + c, f(1) = c
• 例2 输入 f(n) = f(n - 1) + n, f(1) = c
• 例3 输入 f(n) = f(n - 1) + n + c, f(1) = c