递归究竟是什么？如何快速编写正确的递归代码？ —— 力扣经典面试题详解
- 一、递归
- 1.1 什么是递归？
- 1.2 为什么会用到递归？
- 1.3 如何快速编写正确的递归代码？
- 二、力扣相关笔试题解析
- [面试题 08.06. 汉诺塔问题](https://leetcode.cn/problems/hanota-lcci/description/)
- [21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/description/)
- [LCR 024. 反转链表](https://leetcode.cn/problems/UHnkqh/description/)
- [24. 两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/description/)
一、递归
1.1 什么是递归？
下面是来自百度百科对递归算法的定义：
递归是一种算法设计技术，它允许一个函数在其定义或说明中有直接或间接调用自身的方法。
递归在数学和计算机科学中有着广泛的应用，它通过将复杂问题分解为规模较小、形式相同的子问题来求解。递归的基本原理包括：每一级的函数调用都有自己的变量；每一次函数调用都会有一次返回；递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序；递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反；虽然每一级递归都有自己的变量，但是函数代码并不会得到复制。
简单来说，递归的本质就是函数自己调用自己！
1.2 为什么会用到递归？
在回答这个问题前，我们先来看看二叉树的先序遍历是如何实现的？
所谓先序遍历即依次遍历二叉树的根节点、左子树、右子树。在遍历过程中，我们发现左子树和右子树的遍历同样可以采用先序遍历来实现。即将先序遍历整颗二叉树转化先遍历完根节点后，在先序遍历来遍历左子树、右子树。而在先序遍历左/右子树时，我们可以将左子树和右子树当成一颗完整的二叉树，重复上述的过程，直到为空才结束。
在求解问题时，我们发现可以将主问题可以分解为若干个相同的子问题，而这些子问题同样都可以分解为若干个相同的子子问题，不断重复。换句话说，假设我们可以通过一个方法f（可以将f想象成数学中求解问题的函数表达式f(x)）来求解主问题，而主问题所转化出的子问题同样可以通过方法f来解决（而子问题所衍生出的子子问题同样可以通过方法f来解决，不断重复下去），从而实现函数自己调用自己！当面临这种情况时，即可使用递归算法来解决问题。
1.3 如何快速编写正确的递归代码？
- 找到相同的子问题，该过程决定了函数头的设计（即函数参数需要传哪些）
- 将其中一个子问题进行分析，在此过程中将递归函数当作一个黑盒，该函数能完成我们所赋予的功能。该过程决定了函数的函数体。
- 最后当然是返回值了。在何种情况下，递归结束。
下面以二叉树的先序遍历为例进行分析：
首先先序遍历过程：根、左子树、右子树。而左子树和右子树显然是一个相同的子问题（左子树和右子树还可以继续细分下去，都行相同子问题，就不多说了）。所有我们需要给函数传一个根节点参数，用于分割整颗二叉树。
void TreePrev(TreeNode* root)//函数头
现在我们赋予了该递归函数功能：先序遍历二叉树。现在我们取其中一个子问题进行分析，首先我们需要遍历根节点，然后可以通过该递归函数来实现左子树、右子树的先序遍历了，即：
cout << root -> val <<" ";//根节点
//我们赋予了函数TreePrev先序遍历二叉树的功能，所有我们可以把该函数当作一个黑盒。
//只要我们将二叉树的根节点传入该黑盒，便可实现这颗二叉树的先序遍历。（实际该过程可以由画递归展开图验证，由于篇幅问题博主就不多说了）
TreePrev(root -> left);//遍历左子树
TreePrev(root -> right);//遍历右子树
最后就是递归什么时候结束了。显然当根节点未空指针时，递归结束。此时返回空即可
if(root == nullptr)
return;
所以整体代码就是：
void TreePrev(TreeNode* root)//函数头
{
if(root == nullptr)
return;
cout << root -> val <<" ";//根节点
//我们赋予了函数TreePrev先序遍历二叉树的功能，所有我们可以把该函数当作一个黑盒。
//只要我们将二叉树的根节点传入该黑盒，便可实现这颗二叉树的先序遍历。（实际该过程可以由画递归展开图验证，由于篇幅问题博主就不多说了）
TreePrev(root -> left);//遍历左子树
TreePrev(root -> right);//遍历右子树
}
二、力扣相关笔试题解析
面试题 08.06. 汉诺塔问题
【分析】：
题目指让A柱子中的N个圆盘（自下而上降序）借助B转移到C柱子上，并且保存顺序不变。所以我们可以考虑将A柱子上的后N-1个圆盘当作一个整体移到B上，然后将A中剩余的最后一个圆盘移到C上；最后在将B盘上的所有圆盘当作一个整体移到C上即可达成目的！
在题目的分析过程中，出现将A上的N-1个圆盘移到B上，将B上的N-1个圆盘移到C上的过程。而这两个步骤显然是一个递归子问题（将一个柱子上的N个圆盘，借助另一个柱子转移到第三个柱子）。由于该过程中是具体圆盘在3根柱子间的移到，所以函数头因有4个参数：柱A、柱B、柱C、移到圆盘个数！！
由于该过程中，我们通过递归函数（黑盒）将A柱上的N-1个圆盘移到B柱上、将A柱上的剩余的最后一个圆盘移到C柱、通过递归函数（黑盒）将B中的所有圆盘移到C柱。所以函数体为：
//_hanota为我们待实现的递归函数，该函数的功能是将将一个柱子上的N个圆盘，借助另一个柱子转移到第三个柱子
//所以将该函数想成一个黑盒，只需向该函数传递正确参数，即可实现对应的功能！（具体由函数展开图证明）
//先将A中前num-1个圆盘借助C移到B
_hanota(A, C, B, num - 1);
//将A剩余的最后一个元素移到C柱子
C.push_back(A.back());
A.pop_back();
//将B上的num-1个圆盘借助A移到C柱子上
_hanota(B, A, C, num - 1);
最后返回值就不多说了，A中只有一个圆盘时，无需解决B，直接将圆盘从A移到C上。
【下面是其中一个子问题的圆盘转移过程图解】：
【代码编写】：
class Solution {
public:
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
_hanota(A, B, C, A.size());
}
void _hanota(vector<int>& A, vector<int>& B, vector<int>& C, int num)
{
if(num == 1)
{
C.push_back(A.back());
A.pop_back();
return;
}
//先将A中前num-1个圆盘借助C移到B
_hanota(A, C, B, num - 1);
//将A剩余的最后一个元素移到C柱子
C.push_back(A.back());
A.pop_back();
//将B上的num-1个圆盘借助A移到C柱子上
_hanota(B, A, C, num - 1);
}
};
21. 合并两个有序链表
【题目】：
【解析】：
这道题目的就是将两个升序的链表合并成一个升序链表，并返回新链表的头节点。
在本题中，我们可以先选出两链表中节点值较小的节点，然后想办法将该链表中剩下的节点和另一条链表合并为升序链表；最后将最开始选出的较小节点的next指向该新合并的新节点即可解决问题。显然将该链表中剩下的节点和另一条链表合并为升序链表就是一个递归子问题，所以可以采用递归方式解决问题。
由于递归子问题是合并两个有序链表，所有函数头传的参数为待合并的两个链表头节点。至于函数体，我们只需挑选出原来两链表中头节点值较小的节点作为新链表的头节点，然后通过递归函数将剩下的元素和另一个链表合并，最后将新链表的头节点的next指向合并链表的头节点。当链表节点为空时，递归结束。
【代码解析】：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//特殊处理
if (list1 == nullptr)
return list2;
if (list2 == nullptr)
return list1;
if (list1->val < list2->val)
{
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
LCR 024. 反转链表
反转链表我们可以将后n-1个节点反转（并返回反转后链表的头节点），然后在将原链表的头结合和新链表链接即可。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
ListNode* newhead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newhead;
}
}
24. 两两交换链表中的节点
这道题本质上和反转链表类似，我们可以先将原链表头两个节点反转，然后利用递归子问题将后续所有节点当成一个完成链表，完成两两交换链表中的节点。最后将交换后的链表和原链表的头两个数据链接即可。（如果链表为空，或只有一个元素，则递归结束）
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr)
return head;
ListNode* newhead = head->next;
head->next = swapPairs(newhead->next);
newhead->next = head;
return newhead;
}
};
