# 递归

递归是计算机科学中的一个重要概念。它是许多其他算法和数据结构的基础。然而，对于许多初学者来说，掌握它可能是一件非常棘手的事情。

探索以下几个问题：

• 什么是递归？它是如何工作的？
• 如何递归地解决问题？
• 如何分析递归算法的时间和空间复杂度？
• 如何更好地运用递归？

# 递归原理

如何实现调用自身的函数。诀窍在于，每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到到子问题无需进一步递归就可以解决的地步。

为了确保递归函数不会导致无限循环，它应具有以下属性：

• 一个简单的基本案例（basic case）（或一些案例） —— 能够不使用递归来产生答案的终止方案。
• 一组规则，也称作递推关系（recurrence relation），可将所有其他情况拆分到基本案例。

# 示例

可以使用迭代的办法轻而易举地解决这个问题，即从字符串的最后一个字符开始遍历字符串。但是如何递归地解决它呢？

首先，可以将所需的函数定义为 printReverse(str[0...n-1])，其中 str[0] 表示字符串中的第一个字符。然后可以分两步完成给定的任务：

• printReverse(str[1...n-1])：以相反的顺序打印子字符串 str[1...n-1] 。
• print(str[0])：打印字符串中的第一个字符。

function printReverse(str) {
  helper(0, str);

  function helper(index, str) {
    if (!str || index >= str.length) {
      return;
    }
    helper(index + 1, str);
    console.log(str[index]);
  }
}

# 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
  helper(0, s);

  function helper(i, s) {
    if (i >= Math.floor(s.length / 2)) {
      return;
    }
    var temp = s[i];
    s[i] = s[s.length - i - 1];
    s[s.length - i - 1] = temp;
    helper(i + 1, s);
  }
};

# 递归函数

对于一个问题，如果存在递归解决方案，我们可以按照以下步骤来实施它。 举个例子，我们将问题定义为有待实现的函数 F(X)，其中 X 是函数的输入，同时也定义了问题的范围。

举一个例子来说明如何递归地解决问题。

我们可以定义函数 swap(head) 以实现解决方案，其中输入的参数 head 指向链表的头节点。而该函数应当返回将链表中每两个相邻节点交换后得到的新列表的头节点 head 。

按照我们上面列出的步骤，我们可以按下面的流程来实现函数：

1. 首先，我们交换列表中的前两个节点，也就是 head 和 head.next；
2. 然后我们以 swap(head.next.next) 的形式调用函数自身，以交换头两个节点之后列表的其余部分。
3. 最后，我们将步骤（2）中的子列表的返回头与步骤（1）中交换的两个节点相连，以形成新的链表。

# 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

给定 1->2->3->4, 你应该返回 2->1->4->3.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
  if (head === null || head.next === null) {
    return head;
  }
  var next = head.next;
  head.next = swapPairs(next.next);
  next.next = head;
  return next;
};

# 递推关系

在实现递归函数之前，有两件重要的事情需要弄清楚:

• 递推关系： 一个问题的结果与其子问题的结果之间的关系。
• 基本情况: 不需要进一步的递归调用就可以直接计算答案的情况。 有时，基本案例也被称为 bottom cases，因为它们往往是问题被减少到最小规模的情况，也就是如果我们认为将问题划分为子问题是一种自上而下的方式的最下层。

一旦我们计算出以上两个元素，再想要实现一个递归函数，就只需要根据递推关系调用函数本身，直到其抵达基本情况。

为了解释以上几点，让我们来看一个经典的问题，杨辉三角（Pascal's Triangle）:

杨辉三角形是排列成三角形的一系列数字。 在杨辉三角形中，每一行的最左边和最右边的数字总是 1。 对于其余的每个数字都是前一行中直接位于它上面的两个数字之和。

下面的插图给出了一个 5 行的杨辉三角：

# 递推关系

让我们从杨辉三角形内的递推关系开始。 首先，我们定义一个函数 f(i,j)，它将会返回杨辉三角形第 i 行、第 j 列的数字。

我们可以用下面的公式来表示这一递推关系：

f(i,j)=f(i−1,j−1)+f(i−1,j)

# 基本情况

可以看到，每行的最左边和最右边的数字是基本情况，在这个问题中，它总是等于 1。 因此，我们可以将基本情况定义如下:

f(i, j) = 1  where  j = 1  or  j = i

# 演示

正如我们所看到的，一旦我们定义了 递推关系 和 基本情况，递归函数的实现变得更加直观，特别是在我们用数学公式表示出这两个元素之后。 下面给出一个例子，展示我们如何用这个公式递归地计算 f(5,3), 也就是 杨辉三角形第 5 行中的第 3 个数。

我们可以将 f(5, 3) 分解为 f(5, 3) = f(4, 2) + f(4, 3)，然后递归地调用 f(4, 2) 和 f(4, 3)：

• 对于调用的 f(4, 2)f(4,2)，我们可以进一步展开它，直到到达基本情况，正如下面所描述的：

  f(4, 2) = f(3, 1) + f(3, 2) = f(3, 1) + (f(2, 1) + f(2, 2)) = 1 + (1 + 1) = 3

• 对于调用的 f(4, 3)f(4,3)，类似地，我们可以将其分解为：

  f(4, 3) = f(3, 2) + f(3, 3) = (f(2, 1) + f(2, 2)) + f(3, 3) = (1 + 1) + 1 = 3

• 最后，我们结合上述子问题的结果：

  f(5, 3) = f(4, 2) + f(4, 3) = 3 + 3 = 6

# 下一步

在上面的例子中，您可能已经注意到递归解决方案可能会导致一些重复的计算，例如，我们重复计算相同的中间数以获得最后一行中的数字。 举例说明，为了得到 f(5, 3)的结果，我们在 f(4, 2)和 f(4, 3) 的调用中计算了 f(3, 2) 两次。

如何避免这些重复计算（duplicate calculations）。

# 杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    
};