递归

概念

递归并不是一种数据结构，也不指某个具体的算法，而是一种编程写法。

递归是一个函数在其内部直接或间接调用自身，在遇见边界条件时终止递归。

什么场景下可以使用递归呢？

首先是问题可以拆分成子问题，并且大问题和子问题的解决思路是一样的，只是数据不同而已，这样就可以通过同一个函数去解决。

其次，子问题拆分到某个地步应该是不能再拆分了，这样才可以停止继续调用这个函数，避免程序一直执行下去。

递归在某种程序上可以看做是数学归纳法的体现。

数学归纳法

数学归纳法是一种证明数学命题的常用方法，通常用于证明自然数集上的命题。它基于两个关键思想：

归纳假设（Inductive Hypothesis）：假设当某个命题对于某个特定的自然数 n 成立时，它也对于 n+1 成立。
基础情形（Base Case）：证明当 n 等于某个特定的自然数时，命题成立。

数学归纳法的步骤如下：

基础情形证明：首先，证明命题在最小的自然数上成立。这通常是证明当 n 等于 1（或者其他起始自然数）时命题成立的部分。
归纳假设：假设命题对于某个自然数 n 成立，即假设该命题在 n 上成立。
归纳推理：利用归纳假设，证明当 n+1 时命题也成立。通常，这个步骤需要通过利用归纳假设来将 n+1 的情况归结为 n 的情况，以此证明命题对于任意自然数都成立。
结论：基于归纳法的证明，可以得出结论：命题对于所有大于等于基础情形的自然数都成立。

总的来说，数学归纳法允许我们通过逐步迭代的方式，证明某个性质对于所有自然数都成立，而不必逐个检查每个自然数。这使得证明复杂性质的任务变得更为简单和可行。

与遍历对比

遍历是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。

每一次对过程的重复称为一次“遍历”，而每一次遍历得到的结果会作为下一次遍历的初始值，因此遍历是从前往后计算的。

以求1到100的数字和为例，使用遍历，就是通过一个sum变量，记录每次遍历后拿到累加的数字

let sum = 0
for(let i = 1; i< 100;++i){
    sum += i
}

递归则是一步一步往前递推，直到递归结束条件，在这个过程中寻找一条路径，然后再由前向后计算，整个过程有“递”又有“归”。

想一想上面这个1到100的数字和的问题，用递归怎么解？

只要知道了1到99的数字和，再加上100，就是最终的答案
只要知道了1到98的数字和，再加上99，就是1到99的数字和
...
1到1的数字和，就是1

因此，使用递归，就是n + sum(n - 1)

function sum(n) {
  if (n === 1) return 1
  return n + sum(n - 1)
}
sum(100)

虽然遍历和递归都可以解决问题，但是解决问题的思路和过程是完全不同的。

递归思想

我们日常生活中的问题，都是偏线性的，因此我们对于某个问题，很容易尝试使用线性遍历的思想来解决问题。

而递归的概念看起来很简单，但在做题的时候，却不容易写出正确的代码，而到最后看见参考答案时，却又恍然大悟，一看就明白。

这是为什么呢？

递归问题只能以递归的思路理解，需要放弃对于理解和跟踪递归全程的企图，不要尝试跟着计算机执行顺序从第一层运行开始将程序展开。

如果已经确认问题需要通过递归来解决，我们可以按照下面三步来编写代码

首先，找到递归函数的关系式，主要是如何通过子问题求父问题，比如f(n) = n* f(n-1)这样的式子
然后，根据关系式，明确递归函数需要做什么，定义函数的参数和返回值
最后，确认函数的结束条件，一般来说就是最小子问题一眼可以看出来的某个值

这个步骤的难点在于第一步：找到递归函数的关系式。

拿经典的斐波纳契数列（当然还有很多问题不能一眼就看出递归公式，后面会提到）

f(n) = f(n-1) + f(n-2) 
f(0) = 0, f(1) = 1

递归代码就很容易写

function f(n) {
  if (n <= 2) return 1;
  return f(n-1) + f(n-2);
}

自顶向下

回头仔细看一下这个代码中我们拆分子问题的方法。

function f(n) {
  if (n <= 2) return 1;
  return f(n-1) + f(n-2);
}

为了求f(n)，需要知道f(n-1)和f(n-2)，依次向下最后求到f(0)和f(1)。

在解决问题时，从大问题开始逐步分解为小问题，并通过递归调用解决小问题。

这种从原问题向问题边界推导的过程，称为自顶向下的递归。

这个过程中，存在很多重复调用，比如在求f(6)和f(5)的时候，都需要求f(4)，分别对应f(6)的f(n-2)和f(5)的f(n-1)。

常见的优化是使用一个额外的数据结构（通常是字典或数组）来保存已经解决过的子问题的结果，以避免重复计算。

const cache = {}
function f(n) {
  if (cache[n]) return cache[n]
  if (n <= 2) return 1;
  cache[n - 1] = f(n - 1)
  cache[n - 2] = f(n - 2)
  return cache[n - 1] + cache[n - 2]
}

这种方法一般更直观易懂，代码编写也更为简单。但是存在一定的空间开销，因为需要额外的存储空间来保存解决过的子问题的结果。

自底向上

另外还有一种思路，既然知道了f(0)和f(1)，那么也可以正着求f(2)直到f(n)

function f(n) {
  const dp = []
  dp[0] = 0
  dp[1] = 1
  for (let i = 2; i <= n; ++i) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

这种从问题边界向原问题推导的过程，也被称做自底向上的递归，或者递推，一种更为大家熟知的递推，叫做动态规划。

与自顶向下相反，自底向上是从最小的子问题开始解决，然后逐步构建大问题的解。通常使用循环来迭代地解决子问题，直到解决整个问题。

自底向上没有「拆分问题」的过程，直接从一个问题最小的规模开始，一步一步通过「递推」的方式得到原问题的答案。

这种方法一般不需要额外的存储空间来保存子问题的解，因为每次都是根据之前计算的结果来推导新的结果，因此，通常更加高效，尤其是在空间复杂度方面。

由于本篇文章主要介绍递归，因此这里就不再过多介绍动态规划相关的内容了。

从这里可以看出，通过拆分子问题解决大问题的方式，可能有多种思路，在面对具体问题的时候，需要采用合适的方法。

递归函数的前后

也成为前序和后序的位置

比如：倒序打印一个数组。

首先拆分要拆分子问题:

当索引值移动到最后一个元素时，显然直接打印最后一个元素就可以了；
否则，先打印最后一个元素，然后倒序打印前n-1个元素

公式是：f(n) = print(n) + f(n-1)

function print(nums) {
  function dfs(n) {
    if (n < 0) return
    console.log(nums[n])
    dfs(n - 1)
  }
  dfs(nums.length - 1)
}
print([1,2,3])

另外一种写法，从索引值0开始

function print2(nums) {
  function dfs(n) {
    if (n > nums.length - 1) return
    dfs(n + 1)
    console.log(nums[n])
  }
  dfs(0) // 从0开始
}
print2([1,2,3])

前序的地方就是代码首次访问某个元素的位置，而后序就是代码将要离开某个元素的位置。

这在树等数据结构的遍历时更为常用。

后序的特殊性

与前序相比，除了代码位置的差别之外，后序还有一个特殊的功能：它可以访问到子问题递归函数的返回值！

对于那些需要处理子问题的结果的问题，递归的后序位置就尤为重要。这也考虑我们如何设计递归函数的返回值。

常见的递归问题

第一类问题：问题的定义是按递归定义的

比如求阶乘、斐波纳契数列，这种问题即可用遍历解决，也可以用递归解决

第二类问题：问题解法按递归算法实现

比如汉诺塔，需要将问题拆成最小的子问题

第三类问题：数据的结构是按递归定义的

主要是树和图等，很多算法教程建议从树的题目开始练习，就是因为树的结构，天然就要求我们使用递归的思想来解决问题。

汉诺塔

这是一个经典的递归题目。

有一座塔，塔里面呢有三个座A,B,C，座A上放着N个大小不等的盘，其中大盘在下，小盘在上。现在有一个人，希望把盘从A移到B上，但一次只能搬一个盘，而且搬的盘只能放在其他两个盘上，且大盘不能压在小盘上。用程序模拟该过程。

只有一个盘子的时候，直接将A移动到C就好了

console.log('a->c')

当有两个盘子的时候，

将小盘子从A移动到中间B上面
将大盘子从A移动到C上面
将小盘子从B移动到C

console.log('a->b')
console.log('b->c')
console.log('a->c')

不论有多少个盘子，我们最后都会经历这个步骤

借助C，将上面的n-1个盘子都挪到B上面
将第n个盘子从A移动到C上面，A现在就空出来了
借助A，将B上面的n-1个盘子都挪到C上面

因此，最后的代码就是

function move(n, a, b, c) {
  if (n === 1) {
    console.log(`${a}->${c}`)
    return
  }
  move(n - 1, a, c, b)
  console.log(`${a}->${c}`)
  move(n - 1, b, a, c)
}
move(3, 'a', 'b', 'c')

下面是一个可视化的汉诺塔展示

数量：速度：

回文链表

234. 回文链表

判断一个链表是否是回文链表，如果是使用遍历的思想，那就是使用数组，遍历每个节点并保存节点的值，然后使用左右指针一前一后对比节点值是否相等就可以判断是否是回文

// 迭代
var isPalindrome = function (head) {
    var arr = []
    while (head) {
        arr.push(head.val)
        head = head.next
    }
    let l = 0, r = arr.length - 1
    while (l < r) {
        if (arr[l] !== arr[r]) {
            return false
        }
        l++
        r--
    }
    return true
};

实际上，使用递归也可以解决这个问题。

把链表看做是单个节点的树，那么，在后序遍历的地方就可以实现倒序访问链表的功能。这样只需要使用一个额外的frontPointer变量，一前一后对比节点值是否相等就可以判端是否是回文

// 递归
var isPalindrome = function (head) {
    let frontPointer = head;
    function dfs(node) {
        if (node) {
            if (!dfs(node.next)) {
                return false
            }
            if (node.val !== frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true
    }
    return dfs(head)
}

递归 ​

概念 ​

数学归纳法 ​

与遍历对比 ​

递归思想 ​

自顶向下 ​

自底向上 ​

递归函数的前后 ​

后序的特殊性 ​

常见的递归问题 ​

汉诺塔 ​

回文链表 ​

递归

概念