递归树方法

递归是计算机科学和数学中的一个基本概念，它允许函数调用自身，通过迭代步骤解决复杂问题。递归树是理解和分析递归函数执行的一种常用可视化表示。在本文中，我们将探讨递归树的理论、结构及其在理解递归算法中的重要性。

什么是递归树？

递归树是一种图形表示，它说明了递归函数的执行流程。它以视觉方式分解递归调用，展示了算法在分支并最终达到基本情况时的进展。树结构有助于分析时间复杂度和理解所涉及的递归过程。

树结构

递归树中的每个节点都代表一个特定的递归调用。初始调用位于顶部，随后的调用在其下方分支。树向下生长，形成一个分层结构。每个节点的分支因子取决于函数中进行的递归调用次数。此外，树的深度对应于达到基本情况之前进行的递归调用次数。

基本情况

基本情况是递归函数的终止条件。它定义了递归停止并函数开始返回值的时间点。在递归树中，表示基本情况的节点通常被描绘为叶节点，因为它们不会导致进一步的递归调用。

递归调用

递归树中的子节点表示函数中进行的递归调用。每个子节点对应一个单独的递归调用，从而创建新的子问题。传递给这些递归调用的值或参数可能不同，导致子问题的特性发生变化。

执行流程

遍历递归树可以深入了解递归函数的执行流程。从根节点的初始调用开始，我们沿着分支到达随后的调用，直到遇到基本情况。当达到基本情况时，递归调用开始返回，并且它们在树中的相应节点被标记为返回值。遍历一直持续到整个树都被遍历。

时间复杂度分析

递归树有助于分析递归算法的时间复杂度。通过检查树的结构，我们可以确定进行的递归调用次数以及每个级别完成的工作。此分析有助于理解算法的整体效率，并识别任何潜在的低效率或优化机会。

引言

• 考虑一个确定数字阶乘的程序。此函数接受数字 N 作为输入，并返回 N 的阶乘作为结果。此函数的伪代码将类似于：

• 前面提到的函数是递归的示例。我们正在调用一个函数来确定数字的阶乘。然后，给定相同数字的较小值，此函数会调用自身。这会一直持续到我们达到基本情况，即不再有函数调用。
• 递归是一种处理复杂问题的技术，当结果取决于同一问题的较小实例的结果时。
• 如果我们考虑函数，如果一个函数在达到基本情况之前不断调用自身，则称其为递归函数。
• 任何递归函数都有两个主要组成部分：基本情况和递归步骤。一旦达到基本情况，我们就会停止进入递归阶段。为了防止无限递归，基本情况必须正确定义并且至关重要。无限递归的定义是永不达到基本情况的递归。如果程序永不达到基本情况，则会持续发生堆栈溢出。

递归类型

一般来说，递归有两种不同的形式

• 线性递归
• 树递归
• 线性递归

线性递归

• 每次执行时只调用自身一次的函数称为线性递归。阶乘函数是线性递归的一个很好的例子。“线性递归”这个名称指的是线性递归函数执行所需的时间量是线性的。
• 请看下面的伪代码

• 如果我们查看函数 doSomething(n)，它接受一个名为 n 的参数并执行一些计算，然后再次调用相同的过程，但值更小。
• 当使用参数值 n 调用方法 doSomething() 时，假设 T(n) 表示完成计算所需的总时间量。为此，我们还可以制定一个递归关系，T(n) = T(n-1) + K。K 在这里作为常数。包含常数 K 是因为函数分配或释放变量内存或执行数学运算需要时间。我们使用 K 来定义时间，因为它非常微小且微不足道。
• 此递归程序的时间复杂度可以简单地计算，因为在最坏情况下，方法 doSomething() 被调用 n 次。正式地说，函数的时间复杂度为 O(N)。

树递归

• 当你在递归情况下多次进行递归调用时，这被称为树形递归。斐波那契数列是树形递归的一个有效示例。树形递归函数以指数时间运行；它们的时间复杂度不是线性的。
• 请看下面的伪代码，

• 此代码与前一个代码的唯一区别在于，它对同一个函数进行了另一次调用，但 n 的值更小。
• 我们将 T(n) = T(n-1) + T(n-2) + k 作为此函数的递归关系。K 再次作为常数。
• 当对同一个函数进行多次调用，且值较小时，这种递归称为树形递归。现在有趣的地方来了：这个函数有多耗时？
• 根据下面相同的函数的递归树进行猜测。
  
• 你可能会觉得直接查看递归函数来估计时间复杂度很困难，尤其是当它是树形递归时。递归树方法是计算此类函数时间复杂度的几种技术之一。让我们进一步详细检查它。

什么是递归树方法？

• 递归树方法用于解决递归关系，例如 T(N) = T(N/2) + N 或我们在递归类型部分讨论的两个。这些递归关系通常使用分治策略来解决问题。
• 当一个大问题被分解成更小的子问题时，整合这些更小的子问题的解决方案需要时间。
• 例如，对于归并排序，递归关系是 T(N) = 2 * T(N/2) + O(N)。合并两个总大小为 T(N/2) 的子问题的解决方案所需的时间是 O(N)，这在实现级别也是如此。
• 例如，由于二分查找的递归关系是 T(N) = T(N/2) + 1，我们知道二分查找的每次迭代都会导致搜索空间减半。一旦确定结果，我们就会退出函数。递归关系添加了 +1，因为这是一个常数时间操作。
• 要考虑的递归关系是 T(n) = 2T(n/2) + Kn。Kn 表示合并 n/2 维子问题的解决方案所需的时间。
• 让我们描绘前面提到的递归关系的递归树。

从研究上述递归树，我们可以得出一些结论，包括

1. 确定节点值时，只关注每个级别问题的规模。问题规模在级别 0 为 n，在级别 1 为 n/2，在级别 2 为 n/2，依此类推。

2. 通常，我们将树的高度定义为等于 log(n)，其中 n 是问题的规模，此递归树的高度等于树中的级别数。这是因为，正如我们刚才建立的，递归关系使用分治策略来解决问题，并且从问题规模 n 到问题规模 1 只需 log(n) 步。

• 例如，考虑 N = 16 的值。如果我们允许在每个步骤中将 N 除以 2，需要多少步才能得到 N = 1？考虑到我们每一步都除以 2，正确答案是 4，即 log(16) 以 2 为底的值。

log(16) 以 2 为底

log(2^4) 以 2 为底

4 * log(2) 以 2 为底，因为 log(a) 以 a 为底 = 1

所以，4 * log(2) 以 2 为底 = 4

3. 在每个级别，递归中的第二个项被视为根。

尽管此策略的名称中包含“树”一词，但您无需成为树专家即可理解它。

如何使用递归树解决递归关系？

递归树技术中子问题的成本是解决子问题所需的时间量。因此，如果您看到与递归树相关的“成本”一词，它只是指解决特定子问题所需的时间量。

让我们通过几个例子来理解所有这些步骤。

示例

考虑递归关系，

T(n) = 2T(n/2) + K

解决方案

给定的递归关系显示以下属性，

问题规模 n 被分成两个子问题，每个子问题规模为 n/2。合并这些子问题的解决方案的成本是 K。

每个 n/2 的问题规模被分成两个子问题，每个子问题规模为 n/4，依此类推。

在最后一层，子问题规模将减小到 1。换句话说，我们最终达到了基本情况。

让我们按照步骤解决这个递归关系，

步骤 1：绘制递归树

步骤 2：计算树的高度

我们知道，当我们不断地将一个数字除以 2 时，总会有这个数字减小到 1 的时候。与问题规模 N 相同，假设经过 K 次除以 2 后，N 等于 1，这意味着 (n / 2^k) = 1

这里 n / 2^k 是最后一层的问题规模，它总是等于 1。

现在我们可以通过对两边取 log() 很容易地从上面的表达式中计算出 k 的值。下面是更清晰的推导，

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) 以 2 为底

所以树的高度是 log(n) 以 2 为底。

步骤 3：计算每个级别的成本

• 级别 0 的成本 = K，合并了两个子问题。
• 级别 1 的成本 = K + K = 2*K，合并了两个子问题两次。
• 级别 2 的成本 = K + K + K + K = 4*K，合并了两个子问题四次。依此类推……

步骤 4：计算每个级别的节点数

我们首先确定最后一层的节点数。从递归树中，我们可以推导出这一点

• 级别 0 有 1 (2^0) 个节点
• 级别 1 有 2 (2^1) 个节点
• 级别 2 有 4 (2^2) 个节点
• 级别 3 有 8 (2^3) 个节点

因此，级别 log(n) 应该有 2^(log(n)) 个节点，即 n 个节点。

步骤 5：汇总所有级别的成本

• 总成本可以写成，
• 总成本 = 除最后一层外的所有层成本 + 最后一层成本
• 总成本 = 级别 0 成本 + 级别 1 成本 + 级别 2 成本 + .... + 级别 log(n) 成本 + 最后一层成本

最后一层的成本单独计算，因为它是基本情况，并且在最后一层没有进行合并，因此，解决此级别的单个问题的成本是某个常数值。我们将其视为 O(1)。

让我们将值代入公式，

• T(n) = K + 2*K + 4*K + .... + log(n) 次 + O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) 次) + O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) 次) + O(n)

如果你仔细观察上面的表达式，它形成了一个等比数列（a, ar, ar^2, ar^3 ...... 无限次）。等比数列的和由 S(N) = a / (r - 1) 给出。这里 a 是第一项，r 是公比。