C++ 树列表递归大问题

2025年3月17日 | 阅读 7 分钟

在本文中，我们将通过几个例子讨论 C++ 中的大树列表问题。

引言

设想一个计算数字阶乘的程序。此函数接收数字 N 作为输入，并返回 N 的阶乘作为结果。此函数的伪代码将类似于

示例

#include <iostream>
using namespace std;

int sumOfNaturalNumbers(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }

    // Recursive step
    return n + sumOfNaturalNumbers(n - 1);
}

int main() {
    int n = 5; // Calculate the sum of natural numbers from 1 to 5
    int result = sumOfNaturalNumbers(n);
    cout << "Sum of natural numbers from 1 to " << n << " is: " << result << endl;
    return 0;
}

输出

Sum of natural numbers from 1 to 5 is: 15

说明

前面提到的函数就是递归的一个例子。我们正在调用一个函数来计算数字的阶乘。然后，该函数会用这个数字的较小值来调用自身。它会一直持续下去，直到我们到达基本情况，此时不再有函数调用。
递归是一种处理复杂问题的方法，其中结果取决于同一问题较小实例的结果。
如果考虑函数，如果一个函数一直调用自身直到达到基本情况，那么它就被称为递归函数。
任何递归函数都有两个主要组成部分：基本情况和递归步骤。
一旦我们到达基本情况，我们就停止进入递归阶段。必须仔细定义基本情况，并且它们对于防止无限递归至关重要。无限递归的定义是永远无法到达基本情况的递归。如果程序永远无法到达基本情况，堆栈溢出将持续发生。

递归类型

递归主要有两种类型

线性递归
树递归

1. 线性递归

每次执行时只调用自身一次的函数称为线性递归。阶乘函数是线性递归的一个很好的例子。“线性递归”这个名称指的是线性递归函数需要线性时间来执行。

示例

让我们看看下面的伪代码

#include <iostream>
using namespace std;

void countdown(int n) {
    // Base case to stop recursion
    if (n == 0) {
        return;
    }

    // Print the current value
    cout << n << " ";

    // Recursive step
    countdown(n - 1);
}

int main() {
    int n = 5; // Countdown from 5 to 0
    cout << "Countdown: ";
    countdown(n);
    cout << endl;
    return 0;
}

输出

Countdown: 5 4 3 2 1

说明

在此示例中，最简单的情况是当n等于0时。当 n 等于 0 时，递归结束。在此之后，函数停止进行递归调用。
函数在每次迭代结束时打印n的当前值。我们可以使用符号 K 将打印视为一个常数时间操作。

现在让我们定义时间复杂度的递推关系

T(n) = T(n - 1) + K

当使用n作为参数调用函数时，T(n)表示完成整个计算所需的时间。
使用n - 1进行递归调用所需的时间由T(n - 1)表示。
K表示打印 n 值所需的固定时间。

根据此递推关系，使用参数 n执行函数所需的时间等于使用n - 1进行递归调用所需的时间，再加上打印 n 值所需的固定时间K。在这种情况下，该函数会无意中被调用n 次。

由于此代码的时间复杂度为O(n)，因此完成它所需的时间与n成线性关系。函数接收n次调用，每次调用都会执行固定的工作。

2. 树递归

当你在递归情况中多次进行递归调用时，就称为树递归。斐波那契数列是树递归函数的一个有效示例。树递归函数以指数时间运行；它们的时序复杂度不是线性的。

示例

看看下面的伪代码，

function sumTree(node) {
  if (node === null) {
    return 0; // Base case: an empty tree has a sum of 0
  }

  // Recursive step: sum the current node's value with the sums of its left and right subtrees
  return node.value + sumTree(node.left) + sumTree(node.right);
}

// Define a simple binary tree structure
class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

// Create a sample binary tree
const tree = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(3),
    new TreeNode(4)
  ),
  new TreeNode(5,
    null,
    new TreeNode(6)
  )
);

// Calculate the sum of all values in the tree
const treeSum = sumTree(tree);
console.log("Sum of tree values: " + treeSum);

输出

Sum of tree values: 21

说明

在此示例中，除了对具有较小 n 值的同一函数的一次额外调用之外，此函数sumtree(n)与前一个函数几乎相同。
让我们为该函数的递推关系写T(n) = T(n-1) + T(n-2) + k。此处K是另一个常数。
当一个函数被调用多次处理较小值时，这种递归称为树递归。

递归树方法是如何工作的？

递归树策略用于解决诸如 T(N)=T(N/2)+N 或我们之前讨论过的两种（递归类型部分中的线性递归和树递归）之类的递推关系。这些递推关系处理问题的常用方法是分治法。

当一个大问题被分解成更小的子问题时，需要时间来整合这些子问题的答案。

例如，T(N)=2T(N/2)+O(N)是归并排序的递推关系。在实现层面，将两个大小为T(N/2)的子问题的答案合并所需的时间是O(N)。在归并排序的归并步骤中，我们将两个已排序的数组合并以在线性时间内创建一个新的已排序数组。

例如，二分查找的递推关系是T(N)=T(N/2)+1，我们知道二分查找的每次重复都会将搜索空间减半。一旦确定了结果，我们就退出函数。因为这是一个常数时间操作，所以向递推关系中添加+1 +1。

考虑递推关系T(n)=2T(n/2)+Kn。Kn表示组合 n/2 维子问题答案所需的时间。

让我们描绘上述递推关系的递归树。

The Great Tree List Recursion Problem in C++

通过研究上面的递归树，我们可以得出一些结论，包括

确定节点的值时，只需要考虑每个层级的问题大小。问题大小在第 0 层是n，在第 1 层是n/2和n/2，依此类推。
通常，我们将树的高度定义为等于log(n)，其中 n 是问题的大小，而此递归树的高度等于树的层数。这是正确的，因为正如我们刚才建立的，递推关系使用分治策略来解决问题，并且从问题大小 n 到问题大小 1 只需要log(n)次。
在每个层级，我们将递推关系中的第二项视为根。
即使此方法名称中包含“树”一词，我们也不需要成为树专家才能理解它。

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

子问题的成本是递归树方法中解决它所需的时间。因此，当“成本”一词与递归树相关时，它指的就是解决子问题所需的时间。

使用递归树方法，必须执行几个步骤来解决递推关系。包括，

绘制递归树以表示给定的递推关系。
应计算递归树的高度。
计算每个层级的成本（解决每个层级子问题所需的时间）。
确定递归树在每个层级上总共有多少个节点。
递归树的成本跨越其所有层级进行累加。

结论

递归是一种处理复杂问题的方法，其中结果取决于同一问题较小实例的结果。
线性递归和树递归是递归的两个主要类型。
递归树方法是解决递推关系的多种方法之一。
这些递推关系本质上只是递归问题的数学定义。递归树方法在解决递推关系时必须遵循几个步骤。

下一主题C++ 中的定时器实现

C++ 树列表递归大问题

引言

递归类型

1. 线性递归

2. 树递归

递归树方法是如何工作的？

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

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 树列表递归大问题

引言

递归类型

1. 线性递归

2. 树递归

递归树方法是如何工作的？

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

结论

相关帖子

查找 C++ 向量中的成员函数

C++ Cerr

C++ using 与 typedef

C++ std::subtract_with_carry_engine

C++ 静态成员

C++ 程序计算矩阵的行列式

C++ std::stod, std::stof, std::stold

C++ 程序计算数组中的逆序对

在 C++ 中绘制不使用浮点运算的圆

C++ 竞争性编程中最常用的 10 个内置函数

订阅 Tpoint Tech

联系信息

关注我们