探讨:何为递归

我们知道,在函数里面调用这个函数自身的方法就是递归。递归可以通过下面的例子形象理解:

排队的时候,假如你想知道你排在多少位,你就去问你前面的人,前面的人又去问他前面的人,一直传下去,直到问到第一个人,再一直传回来——这样你就知道自己的位置了。

这个模型可以用下面的数学公式描述:

对递归有了一个整体的认识后,我们再来看看其过程。递归包括两个过程:递自顶向下,将问题分解归自底向上,将子问题合并

根据函数调用的机制:递的过程中函数不断地调用自身,每次调用的时候都会开辟一个栈帧来保存这次调用的信息;归的时候恢复当前栈帧,函数执行结束之后销毁这个栈帧然后再恢复上一个栈帧。

递归的一个典型例子就是计算斐波拉契数列的第n项值

问题:

已知斐波拉契数列的第一项和第二项分别为0和1,递推公式为$F(n)=F(n-1)+F(n-2)$,求第n项的值。

代码似乎也很优美,简直就是照搬问题的公式,可读性强。(P:忘了斐波拉契的英文就直接用Fabric代替了,Fabric yyds!)

1
2
3
4
int Fabric(int n){
if(n==0||n==1) return n;
return Fabric(n-1)+Fabric(n-2);
}

但是,其实际结果确是令人高兴失望的:我足足摸了35秒才给我得出n=47的结果!我极度愤怒的情况下用算盘都算得比它快!bushi(

从递推公式$F(n)=F(n-1)+F(n-2)$来看,我们只需要从F(2)线性计算到F(47),消耗的时间复杂度应该是$O(n)$。但从实际的执行效率来看,已经明显不是线性时间复杂度了!

实际上,我们可以用递归树来描述递归的细节:(以n=7为例)啊,少算了个F(2)……

正是由于这样一棵树的结构,该递归的时间复杂度已经达到了指数数量级(由于不是完全二叉树,所以时间复杂度小于$O(2^n)$)——这是由于大量重复计算导致的。这样的重复计算被称为重叠子问题 。我们可以通过一些方法对递归进行剪枝 来减少重复计算,从而降低时间复杂度,这将在下一篇进行讨论。


总结一下:
  1. 递归是一种很精妙的编程方法,它的可读性高,代码也很简洁。
  2. 递归会消耗栈空间。在能进行迭代的情况下,递归开辟的栈空间对问题来说是多余的。我们尽可能使用迭代的方法以降低空间复杂度
  3. 递归可能会导致大量的重复计算,对递归进行剪枝可以减少重复计算的次数。

合并两个有序链表

题目

将两个升序链表合并为一个新的升序链表并返回,新链表是通过拼接给定的两个链表的所有节点组成的:

示例 1:输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]

递归解法

我们先来考虑这个问题的递归解法。

递归三要素
  1. 递归结束的条件。
  2. 对中间情况的一致操作。
  3. 调用函数自身。

我们思考递归解法的时候首先要从对中间情况的一致操作入手,然后思考边界情况是什么,这就是递归结束的条件。

  1. 分析递归的可行性:对于这个问题,我们同样从中间情况开始分析:要合并[1,2,4]和[1,3,4] ,即合并1+[1,2,4]和[3,4] ,即合并1+1+[2,4]和[3,4] ,即合并1+1+2+[4]和[3,4] ,即合并1+1+2+3+[4]和[4] ,即合并1+1+2+3+4和[4] 。可以发现,对子链的合并和初始问题是一样的,所以可以使用递归。

  2. 分析递归需要进行的操作:然后我们分析递归时进行的操作是什么。由于两个链表已经排好序了,所以我们只需要比较首元结点的大小,将较小的那个结点挂到要返回的链表上。

  3. 最后来确定返回条件:当两个链表中的一个已经为空的时候,我们就无需合并了,直接将那个非空的挂到待返回的链表上即可。


这三步的分析下来基本可以解决想要使用递归却无从下手的情况了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1||!l2) return l1?l1:l2;
if(l1->val<=l2->val){
l1->next=mergeTwoLists(l1->next,l2);
return l1
}else {
l2->next=mergeTwoLists(l1,l2->next);
return l2;
}
return nullptr;
}
};
judge

哎,递归的硬伤还是空间啊!

迭代解法

迭代解法要求我们对问题的过程分析得更加具体。我们可以通过分析递归的过程,来思考迭代的解法:

为什么要添加一个头指针?

因为单链表插入到某个位置需要知道这位置的上一个结点,为了保证最初操作和后面操作的一致性,我们定义一个头指针head,最终返回head->next即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1||!l2) return (!l1)?l2:l1;
ListNode* head=new ListNode;
ListNode* pre=head;
while(l1&&l2){
if(l1->val<=l2->val){
pre->next=l1;
l1=l1->next;
}else{
pre->next=l2;
l2=l2->next;
}
pre=pre->next;
}
pre->next=l1?l1:l2;
return head->next;
}
};
judge

迭代解法的空间消耗确实要小一些。

反转链表

题目

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]

这个问题在我之前学习数据结构的链表中的一篇已经写过了:反转链表的方法有迭代法、递归法、头插法和就地逆置法。这篇重点挑递归法来讲一讲,没讲到的方法请跳转:

递归法

我们仍然遵循上面的三步:

  1. 分析递归的可行性:反转[1,2,3,4,5] ,即反转1+[2,3,4,5] ……故反转这个链表可以分解为不断反转这个链表的子链,所以可以使用递归。
  2. 分析递归每步需要进行的操作:对于一个结点,我们让该结点的下一个结点指向这结点,然后让这个结点本身的next指针初始化指向空。(因为第一个结点反转后就是尾节点,需要指向空)
  3. 分析递归结束的条件:当递归的当前结点是链表的最后一个结点时,递归结束。

但是这道题的递归比上一道要难一些,因为这道题的返回值也令人纠结。我们返回的链表的头结点应该是原链表的尾节点,但我们一开始并不知道它的值

我的做法是先一直往下“递”“递”到链表尾节点后使用一个外部变量保存这个值 ,然后在“归”的过程中对这个链表进行反转操作。返回值即返回之前保存的那个外部变量。

实际上反转链表的操作也必须在“归”的过程中完成。因为如果在“递”的过程中反转链表的话,会提前破坏这个链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
ListNode* p=nullptr;
ListNode* reverseList(ListNode* head) {
if(!head||!head->next){
p=head;
return head;
}
reverseList(head->next);
head->next->next=head;
head->next=nullptr;
return p;
}
};
judge

仍然是空间的硬伤!

就地逆置法

这里仅做简单的对比:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr||head->next==nullptr)
return head;
ListNode* root=new ListNode,*temp;
while(temp!=nullptr){
temp=head->next;
head->next=root->next;
root->next=head;
head=temp;
}
return root->next;
}
};
judge

探讨:何时递归

从前面的例子中,我们可以看到递归因为会开辟多余的栈帧,所以其空间消耗大于迭代的方法,而二者时间相当——这时我们应尽可能地不用递归。那么,什么时候应该用递归呢?

再次观察之前那棵递归树 ,黄色标记出计算的顺序(从上至下是递,从下至上是归)

可以发现这个顺序竟然和使用DFS对树进行遍历如出一辙 !没错,递归可以看成使用深度优先搜索的方法对所有可行解进行遍历。自然,当涉及到暴力、枚举、遍历、搜索等的题目就可以使用递归。

值得一提的是,涉及到遍历的题目,非递归的方法通常要借助于栈或队列,这时递归的栈帧就不是多余的了。而且由于递归的栈是程序自动开辟的,所以可能会有编译器的优化,从而使其性能比非递归的高一些(玄学)。递归的更明显优势是程序简洁和可读性强,这时提倡写递归程序。

那什么是回溯呢?

我们知道了递归包括“递”和“归”两个阶段。在“递”的时候对元素进行了操作,回溯就是在“归”的时候把之前的操作复原

这时我们的递归目的不是在原始基础上进行什么改变(毕竟回溯的时候复原了嘛~),而是对所有可行解进行遍历 ,从中搜索 出满足条件的组合——所以这个递归函数的返回值一般都是空


解决回溯问题的最好思路就是先画出递归树

组合

题目

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:输入:n = 4, k = 2 输出:[[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

先画出递归树:

开始之前我们仍然进行递归三问:
  1. 为什么递归?答:因为要对可行的情况进行遍历。
  2. 递归的操作是什么?答:从集合中任意选一个数,然后取所选的数的后面部分作为下次的集合。
  3. 递归的终止条件是什么?答:递归层数为k(初始层数为0)。且结束时收集满足条件的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
void traceback(vector<vector<int>>&vec,vector<int>&nums,int n,int k,int depth,int begin){
if(depth==k) {
vec.emplace_back(nums);
return;
}
for(int i=begin;i<=n;i++){
nums.emplace_back(i);
traceback(vec,nums,n,k,depth+1,i+1);
nums.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> vec;
vector<int> nums;
traceback(vec,nums,n,k,0,1);
return vec;
}
};
代码分析:
  1. 为什么不在conbine函数进行回溯操作?因为回溯函数的返回值一般为void
  2. 创建的回溯函数参数比较多,所以需要我们事先缕清思路vector<vector<int>>&vec是存储满足条件的组合的数组,且一定是引用;vector<int>&nums是暂时存储当前元素的数组,引用是为了提高性能;nk是题给参数;depth是递归层数,用于判断返回条件;begin用于确定可选区间的开始点。
  3. 如何从区间中选一个数?使用for循环依次取即可。
  4. nums.pop_back()即所谓的回溯操作。
judge

思考:可以不进行回溯操作吗?

回溯是为了还原nums数组。如果我们事先确定好nums数组的大小为k,由于每个结果的长度都为k,所以最终一定会覆盖掉之前的情况,没必要回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
void traceback(vector<vector<int>>&vec,vector<int>&nums,int n,int k,int deepth,int begin){
if(deepth==k) {
vec.emplace_back(nums);
return;
}
for(int i=begin;i<=n;i++){
nums[deepth]=i;
traceback(vec,nums,n,k,deepth+1,i+1);
}
}
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> vec;
vector<int> nums(2,0);
traceback(vec,nums,n,k,0,1);
return vec;
}
};
judge

全排列

题目

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

画出递归树:

递归三问:
  1. 为什么递归?遍历。
  2. 递归的操作?从区间集合中选一个数,并将剩下的作为下次的集合。
  3. 递归结束条件?深度为3(实际上,深度为2即可,初始深度为0)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
void dfs(vector<vector<int>>& vec,vector<int>& nums,int depth,const int len) {
if(depth==len-1) {
vec.emplace_back(nums);
return;
}
for(int i=depth;i<nums.size();i++) {
swap(nums[depth],nums[i]);
dfs(vec,nums,depth+1,len);
swap(nums[depth],nums[i]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> vec;
dfs(vec,nums,0,nums.size());
return vec;
}
};

模式和上一题都是一样的,不过这道题没有新建暂存数组,而是通过交换题给数组中元素顺序。

judge


反正这种题套路性太强了,基本上都是一个模式。理解了为什么这么做写出的自然而然就像模板了。