1. 前言
递归解法总是给人一种“只可意会不可言传”的感觉，代码一看就懂，自己动手一写就呆住了，很难受。究其原因，一是我们练习不够，二是理解不够。
2. 什么是递归
递归的例子在平时生活中很容易见到，比如：
开个玩笑
什么是递归呢？函数在运行时调用自己，这个函数就叫递归函数，调用的过程叫做递归。
比如定义函数 f(x)=x+f(x-1)f(x)=x+f(x−1)：
<code>def f(x):
return x + f(x-1)/<code>
如果代入 f(2)f(2)：
- 返回 2+f(1)2+f(1)；
- 调用 f(1)f(1)；
- 返回 1+f(0)1+f(0)；
- 调用 f(0)f(0)；
- 返回 0+f(-1)0+f(−1)
……
这时程序会无休止地运行下去，直到崩溃。
如果我们加一个判断语句 x > 0：
<code>def f(x):
if x > 0:
return x + f(x-1)
else: # f(0) = 0
return 0/<code>
这次计算
<code> f(2)=2+f(1)=2+1+f(0)=2+1+0=3f(2)=2+f(1)=2+1+f(0)=2+1+0=3/<code>
我们从中总结两个规律：
- 递归函数必须要有终止条件，否则会出错；
- 递归函数先不断调用自身，直到遇到终止条件后进行回溯，最终返回答案。
3. 例题
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
<code>输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4/<code>
4. 递归解法
我们可以如下递归地定义在两个链表里的 merge 操作（忽略边界情况，比如空链表等）：
也就是说，两个链表头部较小的一个与剩下元素的 merge 操作结果合并。
根据以上规律考虑本题目：
- 终止条件：当两个链表都为空时，表示我们对链表已合并完成。
- 如何递归：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
5. 代码
python：
<code>class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1: return l2 # 终止条件，直到两个链表都空
if not l2: return l1
if l1.val <= l2.val: # 递归调用
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
else:
l2.next = self.mergeTwoLists(l1,l2.next)
return l2/<code>
java：
<code>class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}/<code>c++：
<code>class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
};/<code>6. 复杂度分析
如何计算递归的时间复杂度和空间复杂度呢？其中时间复杂度可以这样计算：
给出一个递归算法，其时间复杂度 O(T)，通常是递归调用的数量记作 R 和计算的时间复杂度的乘积（表示为O(S) ）的乘积：O(T) = R * O(s)
- 时间复杂度O(m+n)。
m 和 n 为 l1 和 l2 的元素个数。递归函数每次去掉一个元素，直到两个链表都为空，因此需要调用 R=O(m + n)R=O(m+n) 次。而在递归函数中我们只进行了 next 指针的赋值操作，复杂度为 O(1)，故递归的总时间复杂度为 O(T) = R * O(1) = O(m+n)。
- 空间复杂度：O(m+n)。
对于递归调用
<code>self.mergeTwoLists()/<code>
当它遇到终止条件准备回溯时，已经递归调用了 m+nm+n 次，使用了 m+nm+n 个栈帧，故最后的空间复杂度为O(m+n)。
7. 相关题目
以下是一些基础但很经典的题目，值得我们好好练习：
- 反转字符串(https://leetcode-cn.com/problems/reverse-string/)
- 汉诺塔问题(https://leetcode-cn.com/problems/hanota-lcci/solution/)
- 两两交换链表中的节点(https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
- 二叉树的最大深度(https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
如有问题，欢迎讨论~
閱讀更多 代碼宇宙 的文章
