关于递归的写法 - 假设法

今日的 LeetCode 每日一题是 25. K 个一组翻转链表
看完题解之后关闭题解自己写的,算我通过了吧(算法这种东西重在积累经验,是不是自己写的问题不大)。
有时间我再整理吧。主要是突然想介绍一下我自己对 递归 的理解。

本篇所有代码语言都为 C++;

递归

其实递归说简单也挺简单的。很好理解,就是套娃,自己调用自己。
递归有几个部分组成:

  • 出口条件

这里 出口条件 是一定要有的,也是专业术语。否则递归将会陷入死循环。
是我自己加入的,不知道有没有这种专业术语。

具体如下:

1
2
3
4
5
6
7
8
9
10
11
void recursion(){
if( /*出口条件*/ ){
return; // 出口,如果有返回值就为出口值;
}

/* 递 操作*/

recursion(); //出口条件之后到最后一个递归调用之间的操作都为 递 操作

/* 归 操作*/
}

形象一点,想象成一条线向下穿过一个一个方块,达到 出口条件 后再旋转一下从下到上回到第一个,递 操作 就是向下时候要做的操作,归 操作 就是向上回去的时候要做的操作。

其中,按照 归 操作 的有无,递归可以分为 尾递归非尾递归

尾递归

尾递归就是这个方法最后一行调用自己,即没有 归 操作

这里以斐波那契数列举例子:

斐波那契数列具有以下特点:

  • 前两个数字为 1
  • 后面所有数字为前面两个数字之和

我们可以写一个方法来输出该数列的第 n 个数( n 从 0 开始 );

1
2
3
4
5
6
7
8
9
/**
* 斐波那契递归
*/
int fun(int n){
if(n <= 1){
return 1;
}
return fun(n-2) + fun(n-1);
}

这就是一个典型的尾递归,所有的尾递归都可以使用迭代来优化,比如对于以上方法使用迭代来实现就是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 斐波那契迭代
*/
int fun(int n){
int dp[n];
for(int i = 0 ; i < n ; i ++){
if(i <= 1){
dp[i] = 1;
}else{
dp[i] = dp[i-2] + dp[i-1];
}
}
return dp[n];
}

开一个数组来保存之前的斐波那契数。
再多 BB 一点,如果你写 动态规划 的目标函数确定为一元的时候,经常也是这种迭代的形势,dp 也是 动态规划 的简称,约定俗成的一种写法。

假设法

对于 非尾递归 的话就要详细说一下了,我们在打题的时候,遇到的往往也是 非尾递归
关于 非尾递归,很多人都不清楚递归要如何入手,这里我以一道题为例子讲一下我写非尾递归时候的方法:

  • 题目: 206. 反转链表
  • 题目要求递归和迭代两种实现方式,这里我只介绍递归。

以下是我的思考过程:

  1. 明确要用递归。
  2. 明确递归方法的效果:将参数结点之后所有链表都反转并返回新的头节点。
  3. 明确递归方向,即递归方法中调用下一次递归时候传入的参数为当前链表的下一个。

一般明确这三点之后我们就可以开始写了:

方法模型:

1
2
3
ListNode* reverseList(ListNode* head) {

}

出口条件

出口条件也可以分为两个思考过程:

出口条件的思考主要要考虑之前我们明确的这个递归方法要实现的效果,即输入什么,输出什么。

  1. 外部调用时候的出口条件:比如打题的时候系统直接第一次就给你传入一个 null 。当然有些题目中 0 啊之类的,要具体分析。本题中这部分只需要考虑它直接给你 null , 那么我们直接返回一个 null 给它。
  2. 递归过程的出口条件:这里已经假设它给的结点不可能为 null ,则本题中递归过程的出口条件也很容易想到,即结点该结点恰好就是最后一个,则根据之前讲的方法的效果,要返回这一个结点反转后的新头结点,即自己。
1
2
3
if(!head || !(head->next)){
return head;
}

假设成立

我们可以先把递归调用写出来并用一个变量承接返回值。

1
auto *newHead = reverseList(head->next);

考虑一下这个 newHead 是什么,回到我们刚刚讲的明确这个方法的效果, reverseList(node) 方法的效果是将 node 及之后的整条链表反转然后返回新的表头。

虽然我们还没写好这个方法,但是在方法里面,我们可以假设我们已经写完了,它是正常工作的,所以这里的 newHead 是除了第一个结点外后面所有结点都反转好的头节点。

我们的目的是要反转整个链表,然后现在除了第一个之后都反转好了,那么我们接下来只需将第一个接到后面所有反转好的链表后面,然后把这一个下一个置空就可以了。

1
2
3
auto *newHead = reverseList(head->next);
head->next = nullptr; //将第一个结点后一个置空
last->next = head; //将第一个节点接在最后面

写到这里,我们发现 last 还是为止的。想一下我们要怎么拿到 last ,其实也不难想到,我们递归之后后面的所有链表都反转了,所以最初的第一个链表下一个反转后也就是最后一个,所以我们在 递操作 的时候就保存一下这个结点。

1
2
3
4
auto *last = head->next; //先保存递归反转的第一个即反转后最后一个
auto *newHead = reverseList(head->next);
head->next = nullptr; //将第一个结点后一个置空
last->next = head; //将第一个节点接在最后面

大功告成,最后返回反转后的结点头,即返回的 newHead

1
2
3
4
5
auto *last = head->next; //先保存递归反转的第一个即反转后最后一个
auto *newHead = reverseList(head->next);
head->next = nullptr; //将第一个结点后一个置空
last->next = head; //将第一个节点接在最后面
return newHead;

完整代码

1
2
3
4
5
6
7
8
9
10
ListNode* reverseList(ListNode* head) {
if(!head || !(head->next)){
return head;
}
auto *last = head->next; //先保存递归反转的第一个即反转后最后一个
auto *newHead = reverseList(head->next);
head->next = nullptr; //将第一个结点后一个置空
last->next = head; //将第一个节点接在最后面
return newHead;
}

大功告成。

动图说明:

总结

整个过程中,核心就是假设法,假设我们已经写好了这个方法并且可以起作用,然后再补充 递 操作归 操作

有很多递归操作都是这样的,比如 归并排序 的写法,如果你能用假设法,那么你很快就能理解它为什么要怎么写,为什么能这样写。

其次,假设法的思想也可以用于 动态规划 ,只不过 动态规划 抽象出了了 递推公式 这种东西,比较接近解数学题把,但是假设法写递归更偏向于解决实际情景。

身为 一鸽子 ,动态规划 的 Part 2 有空再来更新。