一文详解递归和动态规划，两者结合面试算法题不再怕！

递归和动态规划

动态规划可以理解为是查表的递归（记忆化）。那么什么是递归？什么是查表（记忆化）？

递归

定义： 递归是指在函数的定义中使用函数自身的方法。

算法中使用递归可以很简单地完成一些用循环实现的功能，比如二叉树的左中右序遍历。递归在算法中有非常广泛的使用，包括现在日趋流行的函数式编程。

纯粹的函数式编程中没有循环，只有递归。

有意义的递归算法会把问题分解成规模缩小的同类子问题，当子问题缩写到寻常的时候，我们可以知道它的解。然后我们建立递归函数之间的联系即可解决原问题，这也是我们使用递归的意义。准确来说， 递归并不是算法，它是和迭代对应的一种编程方法。只不过，我们通常借助递归去分解问题而已。

一个问题要使用递归来解决必须有递归终止条件（算法的有穷性），也就是顺递归会逐步缩小规模到寻常。

虽然以下代码也是递归，但由于其无法结束，因此不是一个有效的算法：

def f(n):
  return n + f(n - 1)

更多的情况应该是：

def f(n):
  if n == 1: return 1
  return n + f(n - 1)

练习递归

一个简单练习递归的方式是将你写的迭代全部改成递归形式。比如你写了一个程序，功能是“将一个字符串逆序输出”，那么使用迭代将其写出来会非常容易，那么你是否可以使用递归写出来呢？通过这样的练习，可以让你逐步适应使用递归来写程序。

如果你已经对递归比较熟悉了，那么我们继续往下看。

递归中的重复计算

递归中可能存在这么多的重复计算，为了消除这种重复计算，一种简单的方式就是记忆化递归。即一边递归一边使用“记录表”（比如哈希表或者数组）记录我们已经计算过的情况，当下次再次碰到的时候，如果之前已经计算了，那么直接返回即可，这样就避免了重复计算。而动态规划中 DP 数组其实和这里“记录表”的作用是一样的。

递归的时间复杂度分析

敬请期待我的新书。

小结

使用递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。这里我列举了几道算法题目，这几道算法题目都可以用递归轻松写出来：

• 递归实现 sum

• 二叉树的遍历

• 走楼梯问题

• 汉诺塔问题

• 杨辉三角

当你已经适应了递归的时候，那就让我们继续学习动态规划吧！

动态规划

如果你已经熟悉了递归的技巧，那么使用递归解决问题非常符合人的直觉，代码写起来也比较简单。这个时候我们来关注另一个问题 - 重复计算 。我们可以通过分析（可以尝试画一个递归树），可以看出递归在缩小问题规模的同时是否可能会重复计算。 279.perfect-squares 中 我通过递归的方式来解决这个问题，同时内部维护了一个缓存来存储计算过的运算，这么做可以减少很多运算。 这其实和动态规划有着异曲同工的地方。

小提示：如果你发现并没有重复计算，那么就没有必要用记忆化递归或者动态规划了。

因此动态规划就是枚举所以可能。不过相比暴力枚举，动态规划不会有重复计算。因此如何保证枚举时不重不漏是关键点之一。 递归由于使用了函数调用栈来存储数据，因此如果栈变得很大，那么会容易爆栈。

爆栈

我们结合求和问题来讲解一下，题目是给定一个数组，求出数组中所有项的和，要求使用递归实现。

代码：

function sum(nums) {
   
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  return nums[0] + sum(nums.