大家好,我是多选参数的程序锅,一个正在 neng 操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇将主要介绍递归相关的内容,下面是本篇的内容提纲。
★ 争哥:从我自己学习数据结构和算法的经历来看,我觉得最难理解的知识点,一个是动态规划,另一个是递归。好吧,在众多不太熟练的数据结构和算法中,我也是这两个。 ”
**递归从编程形式上看是函数自己调用自己,是一种编程方法。**很多数据结构和算法的实现都会采用递归这种方式,比如 DFS 深度优先搜索、前中后序二叉树遍历等等。那么怎么理解递归呢?递归其实分为两个过程,去的过程叫过“递”,回来的过程叫做"归"。比如我们坐在电影院里看电影,想知道自己坐的是第几排(别说电影票上有写),那么我们会问前面一排的人,它是第几排,这个过程叫过“递”;之后前面一排的人同样会问再前面一排的人他是第几排,以此类推。当问到第一排的人之后,第一排的人向第二排的人回了个 1,以此类推;我们前面一排的人会给我们回了个第 n-1 排,那么这个过程叫做“归”,从而得到我们是第 n 排。
要想使用递归一定要以下这三个条件,简单来说就是可以分解成子问题,这些子问题的解法和原问题思路一样,有终止条件。
在递归实现代码时,会遇到很多问题,比如堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等问题。
为了避免重复计算,可以使用一个数据结构(比如散列表)来保存已经求解过的 f(k) 值。当递归到 k 的时候判断,f(k) 是否已经求解过了,如果求解过了,那么直接返回,不需要重复计算。
针对上述递归存在的问题,可以将递归代码转化为非递归的形式。**一般来说,递归代码都可以改写成非递归代码的形式。**因为递归本身就是借助栈来实现的,只不过递归使用的是系统栈或者虚拟机提供的。假如我们自己实现一个栈,模拟入栈、出栈的过程的话,那也是可以的(比如图的深度优先比例时可以使用栈和循环来实现,一般情况都是使用递归)。
上述说到了模拟栈的方式,但是在有些递归代码改为非递归代码的形式中,不一定要那么做。**对于同一个问题而言,递归代码是从最大的问题开始,先层层分解,分解完成之后会得到结果,再将结果层层返回,这是有一个有去有回的过程;假如我们知道子问题的答案的话,可以直接从子问题的答案开始,然后子问题求出大的问题的答案,这种相当于只取了归的过程。**比如有这么个递归式:f(n)=f(n-1)+1,终止条件是f(1)=1,那么改为非递归的形式,如下所示。下面这种方式,其实就相当于从子问题的答案出发,从而推得更大问题的解,比如 f(1) = 1,推得 f(2) = f(1)+1=2。
int f(int n) {
int ret = ;
for (int i=; i <= n; ++i) {
ret = ret + ;
}
return ret;
}
从上述的例子中我们可以得出这样一句话,使用递归可以让解决方法更清晰,但是并没有性能上的优势;而使用循环的性能更好。
递归代码的复杂度一般比较难分析,一般可以通过递推公式推导的方式来求解复杂度。但是有时候递推公式推导比较繁琐,这个时候我们可以使用递归树的方式来分析递归算法的复杂度。(个人认为其实掌握递归树即可,递推公式最终也可以转换为递归树,只是递推公式时没有显式的树过程)。
递归的思想就是将大问题分解为小问题来求解,然后再将小问题分解成小小问题。这样一层层分解,直到问题的数据规模被分解得足够小,不用继续递归分解为止。那么将这个过程画成一颗树,这颗树就叫做递归树。
比如斐波那契使用递归的方式求解时,就可以画出下面这样一颗递归树。节点里的数字表示数据的规模,一个节点的求解可以分解为左右子节点两个子问题的求解。
下面通过举几个例子来讲解递归树求解的方法。
归并排序的每次分解都是一分为二,整个递归过程画成递归树之后如图所示。m(n) 的时间复杂度为 m(n/2) 的时间复杂度乘以 2,加上合并所需要的时间复杂度。而 m(n/2) 的时间复杂度等于 m(n/4) 的时间复杂度乘以 2,加上合并所需要的时间度。以此类推,最终时间复杂度为 m(1) 乘以 n,再加上这过程的合并操作所需的时间复杂度。
每一层合并操作所需要的时间复杂度是 O(n),m(1) 的时间复杂度为 O(1)。合并的次数为高度
(从 0 开始算),那么最终时间复杂度为 (高度+1)*O(n)
。从归并排序的原理和递归树来看,归并排序的递归树是一颗满二叉树。那么这颗数的高度为
,因此最终时间复杂度为 O(nlogn)。
快速排序在最好情况下,每次分区都能一分为二,那么此时快速排序的递归树和时间复杂度都和归并排序一样,都是 O(nlogn)。那么,针对不是一分为二的情况。比如很槽糕的情况,每次都是 1:9 的话。那么对应的递归树如图所示。
快速排序时,都需要先分区,然后再递归。在分区时,需要遍历区间内的所有数据。因此,每一层的分区操作所遍历的数据个数之和是 n。同样,我们需要求出树的高度,时间复杂度即为 高度*O(n)
。由于每次分区并不是均匀地一分为二,因此此时的递归树不是满二叉树。但是此递归树最长高度可以求得,即最右边的那个分支,最短高度也可以求得,即最左边的那个分支。从根节点到 q(1),最左边的的深度是
;最右边的深度是
。因此总体的时间复杂度应该位于
和
之间,由于对数复杂度不管底数是多少都可以统一成
,因此快速排序的时间仍然是 O(nlogn)。
假如上述比例变成 1:99,那么类似 1:9 的分析方法,最终的时间复杂度还是 O(nlogn),只要比例是一个常量值之比,那么时间复杂度都是 O(nlogn)。那么平均时间复杂度也是 O(nlogn)。
前文拿斐波那契数列举了个简单的例子,下面我们来完完整整地分析一下斐波那契数列的时间复杂度。斐波那契使用递归的方式实现如下所示
int f(int n) {
if (n == 1){
return 1;
}
if (n == 2) {
return 2;
}
return f(n-1) + f(n-2);
}
将整个递归的过程画成递归树,如图所示。
f(n) 分解为 f(n-1) 和 f(n-2),那么在得到 f(n-1)、f(n-2) 的时间复杂度之后还需要做一个加法操作,该加法操作的时间为 1。那么 f(n-1) 分解成为 f(n-2)、f(n-3) 之后进行加法操作的时间复杂度也是 O(1),因此第二层所需的加法操作时间为 2。依次类推,第 k 层加法时间消耗需要 2^(k-1)。那么,整个算法的时间消耗就是每一层加法的时间消耗之和加上最后的 f(1)、f(2) 所需要的时间操作。
f(n) 分解为 f(n-1) 和 f(n-2),数据规模减少的快慢不一样。最长路径的层次应该是 n 层,最短路径的层次差不多是 2/n 层。因此,最大的时间复杂度为 O(2^n-1),最小的时间复杂度为 O(2^(n/2)-1)。那么,这个算法的时间复杂度介于两者之间,即时间复杂度是指数级的。虽然上述的计算过程不是特别精确,但是时间复杂度的数量级是没有变的。
1 + 2 + ... + 2^(n-1) = 2^n-1
1 + 2 + ... + 2^(n/2-1) = 2^(n/2)-1
全排列的意思是指把 n 个数据的所有排列情况全都找出来。全排列可以采用递归的方式实现:对于 n 个数据的全排列问题,假如我们确定了第一位数据(或者最后一位数据),那么就变成了剩下的 n-1 个数据的排列问题了。并且,第一位数据可以是 n 个数据中的任意一个,即第一位数据有 n 种情况。因此,n 个数据的全排列问题就分解成了 n 个 n-1 个数据全排列的问题了。因此这就满足了递归的前两个条件,即原问题的求解可以分解对成 n 个子问题的求解,并且对于这 n 个子问题的求解方式与原问题的求解方式一模一样,只是数据规模不同。最后是否满足递归的最后一个条件呢?当只剩下 1 个数据的时候,递归可以终止,因此是存在递归终止条件的。
我们将上述的过程写成递归公式如下所示。
f(1, 2, 3, ..., n) = {第一位为1, f(2, 3, ..., n)} + {第一位为2,f(1, 3, ..., n)} + {第一位为n,f(1, 2, ..., n-1)}
将上述的递归公式转化为 Java 代码如下所示
public void fullPermutation(char[] list, int start) {
if (list.length == start) {
System.out.println(list);
}
for (int i = start; i < list.length; i++) {
swap(list, i, start);
fullPermutation(list, start + );
swap(list, i, start);
}
}
public void swap (char[] list, int i, int j) {
char temp;
temp = list[i];
list[i] = list[j];
list[j] = temp;
return;
}
public static void main(String[] args) {
new FullPermutation().fullPermutation(newchar[]{'1', '2', '3'}, );
}
接下去我们使用递归树的方式来对这段代码的时间复杂度进行分析。上述的过程可以画出如下的递归树。第一层有 n 个交换操作,第二层有 n 个节点,每个节点分解需要 n-1 次交换,所以第二层所需要进行交换的次数是 n(n-1)。依次类推,第三层所需要的交换次数是 n(n-1)(n-2),第 k 层所需要的交换次数是 n(n-1)...(n-k+1),最后一层的交换次数是 n(n-1)...2。
最终每一层的交换次数之和就是总的交换次数之和。最后一层的交换次数是 n! 次,而其他层的交换次数肯定小于 n! 次,因此最终的时间复杂度肯定是大于 O(n!),但小于 O(n*n!)。虽然具体的时间复杂度无法求出,但是通过这个范围也可以知道全排列的时间复杂度是很大的。
★ 上述的三个例子,掌握递归树的求解方式才是最重要的,不要纠结于精确的时间复杂度是多少。 另外个人觉得,递归的时间复杂度分析方式只有一种,虽然专栏中说还有递归公式,但是递归公式其实最终也可以转换为递归树,因此最终还是递归树。 ”