本文是对力扣探索卡片 递归 I 的学习记录。
递归算法是一种直接或者间接调用自身函数或方法的算法。
递归算法的实质是把问题分解成“缩小版”子问题，子问题和原题属于同类问题，然后通过递归先求出子问题的解，基于子问题的解最终得到原问题的解。
举个例子，比如原题要求 F(二叉树)，从这个问题可以拆分出两个子问题： F(左子树)、F(右子树)，同样这两个子问题也可以以同样的方式继续拆分，重复这个步骤一直拆分到可解的子问题，再自底向上找到原问题的解。
- 一个问题的解可以分解成 N 个子问题的解。
- 子问题的求解思路除了规模大小之外，与原题没有任何区别。
- 存在递推关系(recurrence relation)，就是一组规则，说明如何将原题的解拆分为子问题的解。
- 存在递归终止条件(base case)。
题目要求很简单：将输入的字符串数组原地反转。
1. 拆解子问题
让我们来看下原题可以拆分成怎样的子问题：
要反转整个数组，我们必须要将 s[0] 和 s[n-1] 进行交换，然后将 s[1] 和 s[n-2] 进行交换，一直重复这个步骤，直到完成数组反转。
从以上思路可以看出来，在递归中我们需要使用两个指针 l 和 r 来指定要进行交换的两个元素下标，在每次递归中，只需要执行 swap(s[l], s[r]) 操作，然后将 l 和 r 分别右移和左移，继续递归。
2. 递归终止条件
- 当两个指针指向同一个元素时，不需要交换，终止递归。
- 当
r指针小于l指针时，说明所有元素都已经完成了交换，终止递归。
- 时间复杂度：$O(N)$，N 为字符串的长度，一共执行了
$N/2$ 次交换。 - 空间复杂度：$O(N)$，N 为字符串的长度，递归过程中使用的栈空间。
JavaScript Code
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function (s, l = 0, r = s.length - 1) {
if (l >= r) return
;[s[l], s[r]] = [s[r], s[l]]
reverseString(s, ++l, --r)
}子问题和 base case
子问题就很明显，F(N) 可以被拆分为 F(N - 1), F(N - 2), ..., F(2), F(1)，其中 F(1) 就是 base case。我们在每步递归中构造出一行，然后推入结果数组，在构造完第 N 行后就得到了原问题的解。
递推关系
第 i 行的数字基于第 i-1 行的数字，具体点是第 i 行第 j 个数字等于第 i-1 行的第 j-1 和第 j 个数字的和：
pascal[i-1][j] = pascal[i-1][j] + pascal[i-1][j-1]
不过有两个特殊的情况，分别是每一行的首尾，它们都是 1。
- 时间复杂度：$O(numRows^2)$。进行了
$numRows$ 次递归，每次递归中遍历数组的时间消耗分别是$1 + 2 + ... + numRows$ ，高斯求和去常数之后结果是$O(numRows^2)$ ；所以最终时间复杂度是$O(numRows^2)$ - 空间复杂度：$O(numRows^2)$。递归过程中使用的栈空间是
$O(numRows)$ ；每一行数组消耗的空间是$O(N)$ ，N 是行数，所以结果数组所占的总空间是$1 + 2 + ... + numRows$ ，也就是$O(numRows^2)$ ；所以最终空间复杂度是$O(numRows^2)$ 。
JavaScript Code
/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function (numRows, res = []) {
if (numRows <= 0) return []
// base case
if (numRows === 1) {
res.push([1])
return res
}
// 当前行的构造依赖于上一行
// 所以要先递归构造出上一行
generate(numRows - 1, res)
// 拿到上一行的结果
// 注意数组是以 0 为初始下标，所以上一行的索引是 numRows - 2
const lastRow = res[numRows - 2]
// 开始构造当前行
const row = Array(numRows).fill(0)
// 特殊情况：数组首尾都是 1
row[0] = row[numRows - 1] = 1
// 根据递推关系构造当前行
for (let i = 1; i < numRows - 1; i++) {
row[i] = lastRow[i - 1] + lastRow[i]
}
// 加入结果中，最后返回结果
res.push(row)
return res
}思路和上一题相差无几，先通过递归拿到上一行的数字，然后基于上一行计算当前行的数字。
不同的是本题只要求返回第 k 行，而且为了
另外还有一个小细节，本题的杨辉三角是从第 0 行开始的。
- 时间复杂度：$O(k^2)$。
- 空间复杂度：$O(k)$。
JavaScript Code
/**
* @param {number} rowIndex
* @return {number[]}
*/
var getRow = function (rowIndex) {
if (rowIndex < 0) return []
if (rowIndex === 0) return [1]
const row = getRow(rowIndex - 1)
let temp = 1
for (let i = 1; i < rowIndex; i++) {
const last = temp
temp = row[i]
row[i] += last
}
row.push(1)
return row
}子问题
要将以 head 为头部的链表进行反转，我们可以先考虑将以 head.next 为头部的这一段链表进行反转，进一步拆分的话，那就是先反转 head.next.next, ..., 直到链表的最后一个节点。
递归终止条件
链表最后一个节点，或者空节点。
递推关系
要找到 F(head) 与 F(head.next) 的关系，F 是一个抽象函数，它的功能是反转链表并返回新链表的头部。
也就是说，当我们递归解决完 F(head.next) 时，已经得到了反转后链表的头部，那回到 F(head) 这一层递归时，我们只需要把 head 拼接到新链表中去，然后直接返回新链表头部就好。
- 时间复杂度：$O(N)$，N 为链表长度。
- 空间复杂度：$O(N)$，N 为链表长度，递归栈的空间。
JavaScript Code
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
if (!head || !head.next) return head
const reversedHead = reverseList(head.next)
head.next.next = head
head.next = null
return reversedHead
}递归中可能存在很多重复的计算，举个简单的例子，斐波那契数列：
F(4) = F(3) + F(2) = (F(2) + F(1)) + F(2)
在上面这个简单的例子中 F(2) 被重复计算了，随着 N 的值增加，重复的计算也会增多。
虽然递归算法非常直观有效，但过多的重复计算也可能会导致性能问题。
记忆化(memoization) 是用来避免递归性能损失的一种常用优化手段，比如我们可以用哈希表来缓存已经计算过的 F(N)，以额外的空间来换取计算时间的减少。
把计算结果存在一个哈希表中，计算 fib(N) 时，如果 N 存在于哈希表中，可以直接返回缓存结果而无需重复计算。
- 时间复杂度：$O(n)$。每个递归函数中都有 2 次递归调用，所以递归树是一个二叉树，进行优化前，我们相当于把二叉树的节点都访问了一遍，所以时间复杂度是
$O(2^n)$ 。使用记忆化优化后，时间复杂度降低为$O(n)$ ，也就是二叉树的高度。 - 空间复杂度：$O(n)$，递归栈的空间是
$O(n)$ ，哈希表的空间也是$O(n)$ 。
JavaScript Code
const cache = {
map: {},
has(N) {
return N in this.map
},
getC(N) {
return this.map[N]
},
put(N, val) {
this.map[N] = val
return val
},
}
/**
* @param {number} N
* @return {number}
*/
var fib = function (N) {
if (N === 0) return 0
if (N === 1) return 1
if (cache.has(N)) return cache.getC(N)
return cache.put(N, fib(N - 1) + fib(N - 2))
}类似题目
根据之前的递归思路，我们很容易可以写出
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function (x, n) {
const helper = (x, n) => {
if (n === 0) return 1
return x * helper(x, n - 1)
}
return n > 0 ? helper(x, n) : 1 / helper(x, -n)
}定义一个 helper 来处理递归计算幂，n 为负数的情况在外层函数处理。
但是这种写法是不能 AC 的，当 n 的值非常大的时候，会发生调用栈溢出错误。所以每次递归的时候 n 不能只减一，这样递归层次太深。
快速幂算法
每次递归 n 都除以 2：
- 当 n 为偶数时，递归结果再平方就是我们要的结果了；
- 当 n 为奇数时，递归结果平方后再乘一个 x 就是我们要的结果。
JavaScript Code
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function (x, n) {
const helper = (x, n) => {
if (n == 0) return 1
// 为什么要用 Math.floor：
// n 为奇数时先考虑 n-1 那部分
// 递归计算 (n-1)/2
// 递归结果平方后再乘一个 x
const r = helper(x, Math.floor(n / 2))
return n % 2 === 0 ? r ** 2 : r ** 2 * x
}
return n >= 0 ? helper(x, n) : 1 / helper(x, -n)
}- 时间复杂度：$O(log n)$，每次递归都会将问题规模减半。
- 空间复杂度：$O(log n)$，递归栈的空间。
首先我们有一个 mergeTwoLists 方法，它的功能就是合并两个链表，并返回新链表的头部。
那么子问题是什么呢？有两种情况：
mergeTwoLists(l1.next, l2)：我们选定l1节点作为新链表的头，然后递归地去合并l1.next这部分和l2。mergeTwoLists(l1, l2.next)：我们选定l2节点作为新链表的头，然后递归地去合并l2.next这部分和l1。
至于选择哪种，取决于 l1 和 l2 节点值的大小。递归结束后再将新链表头和递归结果连接起来。
- 时间复杂度：$O(n + m)$，n 和 m 分别是两个链表的长度。
mergeTwoLists每次最多有 1 次递归，因此时间复杂度取决于合并后链表的长度。 - 空间复杂度：$O(n + m)$，n 和 m 分别是两个链表的长度。
JavaScript Code
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function (l1, l2) {
if (!l1) return l2
if (!l2) return l1
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
}我首先试了最直觉的方法，递归地构造每一行的数字。不过因为每一行数字都翻倍了，这种方法毫不意外报了调用栈溢出错误。
接着我观察了一下，发现如果将第 n 行的数字两两分组，那每一组就分别对应第 n-1 行的一个数字。尝试将第 n 行的下标和第 n-1 行的下标对应起来，那就是
row[n][k] = row[n - 1][((k + 1) / 2) >> 0]
也就是说，第 n 行的第 k 个数字，取决于上一行的第 (k + 1) / 2 个数字。而且，每组中的第一个数字(下标为奇数)与上一行的数字相同，第二个数字(下标为偶数)与上一行的数字相反。
相反的意思是 0 对应 1，1 对应 0。
- 时间复杂度：$O(N)$。
- 空间复杂度：$O(N)$。
JavaScript Code
/**
* @param {number} N
* @param {number} K
* @return {number}
*/
var kthGrammar = function (N, K) {
if (N === 1) return 0
const l = kthGrammar(N - 1, ((K + 1) / 2) >> 0)
// 奇数相同，偶数相反
return K & 1 ? l : l ^ 1
}逐行构造的解法，不能 AC
/**
* @param {number} N
* @param {number} K
* @return {number}
*/
var kthGrammar = function (N, K) {
const helper = N => {
if (N === 1) return '0'
const last = helper(N - 1)
return last.replace(/0|1/g, s1 => (s1 === '0' ? '01' : '10'))
}
return helper(N)[K - 1]
}// TODO: