递归原理

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

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

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

   递归函数

   对于一个问题，如果存在递归解决方案，我们可以按照以下步骤来实施它。

举个例子，我们将问题定义为有待实现的函数 ，其中 是函数的输入，同时也定义了问题的范围。

然后，在函数 中，我们将会：

1. 将问题逐步分解成较小的范围，例如 , , …, ；
2. 调用函数 , , …, 递归地 解决 的这些子问题；
3. 最后，处理调用递归函数得到的结果来解决对应 的问题。

   参考链接

   https://leetcode-cn.com/explore/featured/card/recursion-i/257/recurrence-relation/1208/