递归

递归的使用

不同的递归使用场景

Posted by 雯饰太一 on May 28, 2023

递归的使用

目前个人遇到过的几种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//不带有任何返回参数的递归，通常闭合条件是内定的
void Fun(T* tObj)
{
    if(/*some case*/)
    {
        Fun(newObj);
    }
}

//没有返回参数，但是可以通过一个递归外的量作为退出条件，或作为回收统计机制
void Fun(T* tObj,T2& set1,T3& set2)
{
     if(/*some case*/)
    {
        Fun(newObj, set1, set2);
    }
}

//具备返回值的递归
int Fun(T* a,T* b)
{
    return Fun(a->left, a->right) + Fun(b->left, b->right);
}

其他一些递归的案例

阶乘计算

计算一个正整数的阶乘。例如，n! = n * (n-1) * (n-2) * ... * 1。可以使用递归来计算阶乘，通过将问题分解为更小的子问题。

当计算一个正整数的阶乘时，可以使用递归实现。下面是一个示例代码，演示了如何使用递归来计算阶乘：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>

unsigned long long factorial(unsigned int n) {
    // 递归终止条件：当 n 为 0 或 1 时，阶乘为 1
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // 递归调用，将问题分解为较小的子问题
    return n * factorial(n - 1);
}

int main() {
    unsigned int num;

    std::cout << "Enter a positive integer: ";
    std::cin >> num;

    unsigned long long result = factorial(num);
    std::cout << "Factorial of " << num << " is " << result << std::endl;

    return 0;
}

在上述代码中，factorial 函数使用递归方式计算阶乘。当 n 为 0 或 1 时，递归终止，直接返回 1。否则，递归调用 factorial 函数来计算 (n-1) 的阶乘，并将结果乘以 n，得到 n! 的值。在 main 函数中，用户输入一个正整数，然后调用 factorial 函数来计算其阶乘，并将结果输出。

斐波那契数列

计算斐波那契数列的第 n 个数字。斐波那契数列的定义是，前两个数字是 0 和 1，后续的数字是前两个数字的和。可以使用递归来计算斐波那契数列，通过将问题分解为两个较小的子问题。下面是一个示例代码，展示了如何使用递归来计算斐波那契数列的第 n 个数字：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>

unsigned long long fibonacci(unsigned int n) {
    // 递归终止条件：当 n 为 0 或 1 时，斐波那契数为 n
    if (n == 0 || n == 1) {
        return n;
    }
    
    // 递归调用，将问题分解为两个较小的子问题
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    unsigned int num;

    std::cout << "Enter a positive integer: ";
    std::cin >> num;

    unsigned long long result = fibonacci(num);
    std::cout << "Fibonacci number at position " << num << " is " << result << std::endl;

    return 0;
}

在上述代码中，fibonacci 函数使用递归方式计算斐波那契数列的第 n 个数字。当 n 为 0 或 1 时，递归终止，直接返回 n。否则，递归调用 fibonacci 函数来计算第 n-1 和 n-2 个数字的斐波那契数，并将两者相加得到第 n 个数字。在 main 函数中，用户输入一个正整数，然后调用 fibonacci 函数来计算斐波那契数列中对应位置的数字，并将结果输出。

文件系统遍历

C++ 17

遍历文件系统的目录结构，包括子目录和文件。可以使用递归来遍历文件系统，通过递归地进入子目录并处理每个子目录和文件。

以下是一个递归实现的文件系统遍历的示例代码，可以遍历指定目录下的所有文件和子目录：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <filesystem>

namespace fs = std::filesystem;

void traverseDirectory(const fs::path& path) {
    if (!fs::exists(path)) {
        std::cout << "Path does not exist." << std::endl;
        return;
    }

    if (fs::is_directory(path)) {
        for (const auto& entry : fs::directory_iterator(path)) {
            if (fs::is_directory(entry)) {
                // 递归遍历子目录
                traverseDirectory(entry);
            } else {
                // 处理文件
                std::cout << "File: " << entry.path() << std::endl;
            }
        }
    } else {
        std::cout << "Path is not a directory." << std::endl;
    }
}

int main() {
    std::string directoryPath;
    std::cout << "Enter a directory path: ";
    std::getline(std::cin, directoryPath);

    traverseDirectory(directoryPath);

    return 0;
}

在上述代码中，traverseDirectory 函数使用递归方式遍历指定目录下的所有文件和子目录。首先，检查给定的路径是否存在，如果不存在则输出错误信息并返回。然后，判断给定路径是否为目录，如果是目录，则遍历该目录下的所有条目。对于每个条目，如果是子目录，则递归调用 traverseDirectory 函数继续遍历子目录；如果是文件，则输出文件路径。如果给定路径不是目录，则输出错误信息。

在 main 函数中，用户可以输入一个目录路径，然后调用 traverseDirectory 函数来遍历该目录及其子目录中的文件。

请注意，示例中使用了 C++17 中的文件系统库 <filesystem>，因此需要编译器和标准库支持。如果您的编译环境不支持 C++17 文件系统库，可以考虑使用其他的文件系统操作库，如 Boost.Filesystem 等。

使用QT的方法进行遍历

在 Qt 中，可以使用 QDir 类进行文件系统的递归遍历。以下是一个示例代码，展示了如何使用 QDir 进行递归遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <QCoreApplication>
#include <QDir>
#include <QDebug>

void traverseDirectory(const QString& path) {
    QDir directory(path);

    if (!directory.exists()) {
        qDebug() << "Path does not exist.";
        return;
    }

    directory.setFilter(QDir::AllEntries | QDir::NoDotAndDotDot);
    QFileInfoList fileList = directory.entryInfoList();

    for (const QFileInfo& fileInfo : fileList) {
        if (fileInfo.isDir()) {
            // 递归遍历子目录
            traverseDirectory(fileInfo.filePath());
        } else {
            // 处理文件
            qDebug() << "File: " << fileInfo.filePath();
        }
    }
}

int main(int argc, char *argv[]) {
    QCoreApplication app(argc, argv);

    QString directoryPath = "/path/to/directory";
    traverseDirectory(directoryPath);

    return app.exec();
}

在上述代码中，traverseDirectory 函数使用递归方式遍历指定目录下的所有文件和子目录。首先，创建一个 QDir 对象并指定要遍历的目录路径。然后，设置过滤器为 QDir::AllEntries 表示遍历所有条目，排除 “.” 和 “..” 目录。接下来，获取目录中的文件和子目录的信息列表。对于每个条目，如果是子目录，则递归调用 traverseDirectory 函数继续遍历子目录；如果是文件，则输出文件路径。

在 main 函数中，创建一个 QCoreApplication 对象，并指定命令行参数。然后，设置要遍历的目录路径，并调用 traverseDirectory 函数进行遍历。

请注意，示例中的路径为字符串常量 “/path/to/directory”，请根据实际情况修改为您要遍历的目录路径。此外，需要确保 Qt 库已正确链接到项目中，并在编译和运行时使用了正确的 Qt 版本。

使用QT进行文件遍历时，提高速度的一种做法

如果目录下的文件非常多，直接使用 entryInfoList 可能会导致性能下降。为了解决这个问题，可以采用异步遍历的方式，逐步获取文件信息，从而提高效率。以下是一个示例代码，展示了如何使用异步遍历方式遍历目录：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <QCoreApplication>
#include <QDirIterator>
#include <QDebug>
#include <QThreadPool>

class DirectoryIterator : public QObject
{
    Q_OBJECT
public:
    explicit DirectoryIterator(QObject *parent = nullptr) : QObject(parent) {}

    void traverseDirectory(const QString& path) {
        QDirIterator iterator(path, QDir::AllEntries | QDir::NoDotAndDotDot, QDirIterator::Subdirectories);

        while (iterator.hasNext()) {
            iterator.next();

            if (iterator.fileInfo().isDir()) {
                // 异步遍历子目录
                QThreadPool::globalInstance()->start([this, path = iterator.filePath()] {
                    traverseDirectory(path);
                });
            } else {
                // 处理文件
                qDebug() << "File: " << iterator.filePath();
            }
        }
    }
};

int main(int argc, char *argv[]) {
    QCoreApplication app(argc, argv);

    QString directoryPath = "/path/to/directory";

    DirectoryIterator directoryIterator;
    directoryIterator.traverseDirectory(directoryPath);

    return app.exec();
}

#include "main.moc"

在上述代码中，我们创建了一个名为 DirectoryIterator 的自定义类，继承自 QObject。该类用于执行异步遍历操作。在 traverseDirectory 函数中，我们使用 QDirIterator 对象进行遍历。使用 QDirIterator::Subdirectories 标志表示递归遍历子目录。在遍历过程中，如果遇到子目录，则在全局线程池中启动一个异步任务，继续遍历子目录。对于文件，则直接处理文件。

在 main 函数中，我们创建了一个 DirectoryIterator 对象，并调用 traverseDirectory 函数进行异步遍历。

通过使用异步遍历的方式，我们可以将遍历任务分散到多个线程中，从而提高遍历的效率。请注意，在异步遍历过程中可能会产生并发访问的问题，需要注意线程安全性。

另外，为了支持异步操作，代码中使用了 QThreadPool 全局线程池。确保在项目中正确链接了 Qt 的相关模块，并在编译和运行时使用了正确的 Qt 版本。

关于QDirIterator的部分使用方法

QDirIterator 是 Qt 中用于遍历目录内容的类，它提供了一种简单和高效的方式来获取目录中的文件和子目录的信息。以下是关于 QDirIterator 类的一些详细信息：

构造函数：

  • QDirIterator(const QString &path, QDir::Filters filters = QDir::NoFilter, QDirIterator::IteratorFlags flags = NoIteratorFlags)
  • QDirIterator(const QDir &dir, QDir::Filters filters = QDir::NoFilter, QDirIterator::IteratorFlags flags = NoIteratorFlags)

这些构造函数用于创建 QDirIterator 对象并指定要遍历的目录路径或目录对象。filters 参数用于设置过滤器，指定需要返回的条目类型。flags 参数用于设置迭代器的行为选项。

过滤器（Filters）：

  • QDir::NoFilter：无过滤器，返回所有条目。
  • QDir::Files：只返回文件。
  • QDir::Dirs：只返回目录。
  • QDir::AllEntries：返回所有文件和目录。
  • QDir::NoDotAndDotDot：排除 “.” 和 “..” 目录。

除了上述过滤器，还可以使用其他过滤器组合或自定义过滤器来满足特定的需求。

迭代器标志（IteratorFlags）：

  • QDirIterator::NoIteratorFlags：无特殊标志。
  • QDirIterator::Subdirectories：递归遍历子目录。
  • QDirIterator::FollowSymlinks：跟随符号链接。

这些标志可以与 QDirIterator 的构造函数中的 flags 参数一起使用，以指定迭代器的行为。

成员函数：

  • bool hasNext() const：检查是否还有更多的条目可用。
  • QString next()：返回下一个条目的路径，并将迭代器移到下一个位置。
  • QFileInfo fileInfo() const：返回当前条目的文件信息对象。

这些成员函数可用于遍历目录并获取每个条目的相关信息。

使用 QDirIterator 进行目录遍历时，您可以根据需要设置过滤器和迭代器标志，使用 hasNext 和 next 函数获取每个条目的路径，并使用 fileInfo 函数获取条目的详细信息。

请注意，在使用 QDirIterator 进行目录遍历时，要确保目录存在，并且具有适当的访问权限。

这些是关于 QDirIterator 类的一些基本信息和常用方法。您可以参考 Qt 的官方文档以获取更多详细的信息和示例代码。

树的遍历

遍历树结构的节点，包括二叉树、多叉树等。可以使用递归来遍历树的节点，通过递归地处理每个节点的子节点。

以下是一个基于递归的树结构遍历的示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <iostream>
#include <vector>

struct TreeNode {
    int value;
    std::vector<TreeNode*> children;

    TreeNode(int val) : value(val) {}
};

void traverseTree(TreeNode* node) {
    if (!node)
        return;

    // 处理当前节点
    std::cout << node->value << " ";

    // 遍历子节点
    for (TreeNode* child : node->children) {
        traverseTree(child);
    }
}

int main() {
    // 构建一个树结构
    TreeNode* root = new TreeNode(1);

    TreeNode* node2 = new TreeNode(2);
    TreeNode* node3 = new TreeNode(3);
    TreeNode* node4 = new TreeNode(4);
    TreeNode* node5 = new TreeNode(5);

    root->children.push_back(node2);
    root->children.push_back(node3);

    node2->children.push_back(node4);
    node2->children.push_back(node5);

    // 遍历树结构
    traverseTree(root);

    // 释放内存（树结构的销毁）
    delete node4;
    delete node5;
    delete node2;
    delete node3;
    delete root;

    return 0;
}

上述代码定义了一个简单的树节点结构 TreeNode，其中包含一个值和一个子节点的向量。通过递归的方式，实现了树的遍历功能。

traverseTree 函数用于遍历树结构。首先处理当前节点的值，然后递归遍历每个子节点。

在 main 函数中，构建了一个简单的树结构，并调用 traverseTree 函数进行遍历。最后，释放了动态分配的节点内存，完成树结构的销毁。

运行以上示例代码将输出树结构的遍历结果：1 2 4 5 3。您可以根据需要调整树结构和节点值，并扩展遍历逻辑以满足实际需求。

图的深度优先搜索（DFS）

在图中进行深度优先搜索遍历，访问每个节点并探索其相邻节点。可以使用递归来实现图的深度优先搜索，通过递归地处理每个节点的相邻节点。

以下是一个基于递归的图的深度优先搜索（Depth-First Search, DFS）的示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>
#include <vector>
#include <unordered_set>

class Graph {
public:
    Graph(int numVertices) : vertices(numVertices) {}

    void addEdge(int from, int to) {
        vertices[from].push_back(to);
    }

    void dfs(int startVertex) {
        std::unordered_set<int> visited;
        dfsRecursive(startVertex, visited);
    }

private:
    std::vector<std::vector<int>> vertices;

    void dfsRecursive(int vertex, std::unordered_set<int>& visited) {
        visited.insert(vertex);
        std::cout << vertex << " ";

        for (int adjacentVertex : vertices[vertex]) {
            if (visited.count(adjacentVertex) == 0) {
                dfsRecursive(adjacentVertex, visited);
            }
        }
    }
};

int main() {
    Graph graph(7);

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
    graph.addEdge(2, 6);

    std::cout << "DFS Traversal: ";
    graph.dfs(0);
    std::cout << std::endl;

    return 0;
}

上述代码定义了一个简单的有向图类 Graph，使用邻接表表示图的连接关系。通过递归的方式实现了图的深度优先搜索。

dfsRecursive 函数是递归函数，接收当前顶点和已访问顶点的集合作为参数。首先将当前顶点标记为已访问，然后输出当前顶点的值。接下来，遍历当前顶点的邻接顶点，如果邻接顶点尚未访问，则递归调用 dfsRecursive 函数。

在 main 函数中，创建了一个具有7个顶点的图，并添加了连接关系。然后调用 dfs 函数进行深度优先搜索，并输出遍历结果。

运行以上示例代码将输出深度优先搜索的遍历结果：0 1 3 4 2 5 6。您可以根据需要调整图的顶点和边的连接关系，并扩展遍历逻辑以满足实际需求。

注意

请注意，递归实现中，递归深度会随着输入值的增加而增加，可能导致堆栈溢出。因此，在实际使用递归时，需要注意递归深度的限制，或者考虑使用迭代方法来替代递归。

递归是一种编程技巧，它可以解决许多问题，但也存在一些优劣之处。

优点：

  1. 简洁清晰：递归可以将复杂的问题拆分成更小的子问题，使代码结构更加清晰、简洁。
  2. 可读性强：递归的代码通常具有良好的可读性，因为它可以直接反映问题的本质，使得代码更易于理解和维护。
  3. 解决特定问题：某些问题天然适合使用递归来解决，例如树结构、图遍历等。

缺点：

  1. 性能开销：递归调用涉及函数的堆栈操作，可能会占用大量的内存和额外的时间。递归深度过大时，可能导致堆栈溢出。
  2. 可能引发重复计算：某些递归算法可能会重复计算相同的子问题，导致效率低下。可以通过记忆化技术（如动态规划）来解决这个问题。
  3. 可能导致代码难以理解和调试：过度的递归调用可能导致代码变得复杂，难以理解和调试。在处理复杂问题时，递归的控制流可能变得难以追踪。

注：关于动态规划，后期会逐渐提到

相关资源

以下是一些常用的数据结构可视化网站：

  1. Visualgo: https://visualgo.net/zh - 提供了各种数据结构和算法的可视化演示，包括数组、链表、树、图等。

  2. Data Structure Visualizations: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html - 提供了多种数据结构和算法的可视化演示，包括栈、队列、堆、排序算法等。

  3. Algorithm Visualizer: https://algorithm-visualizer.org/ - 提供了多种数据结构和算法的可视化演示，包括树、排序算法、图算法等。

引入几个，其他功能的网站，如下：

https://www.bejson.com/runcode/cpp920/ 这是一个在线运行代码的网站

https://codebeautify.org/cpp-formatter-beautifier 可以在线美化代码

目录
    特色标签
    QT C++ 编译 VS 网络 python QTreeWidget 良田 cpp 代码片段 函数指针 基础知识 必剪 文案 类型转换 线程 翻译 脚本 转载 DLL Json QWidget TODO cmd git js mixplorer paintEvent
    吾友