C 语言尾递归

计算机编程中的**尾递归**是指一种特定形式的**递归**，其中函数在生成输出之前将其自身作为最后一步调用。简而言之，在**尾递归函数**中，调用自身是函数在给出输出之前所做的最后一件事情。这种特殊的模式允许特定的编程语言和编译器更有效地管理内存。它们可以为即将到来的递归调用重用当前函数的工作空间，从而减少创建新内存段的需求，从而提高程序运行的效率。

这就像你堆书一样。假设你有一堆书，想数一下有多少本。为此，你一次数一本，并记录总数。当你数到最后一本书时，你不是数完后大声说出总数，而是从头开始重新数这堆书，只是在你的总数中又多加了一本书。

这样，在你数完所有书（包括你刚刚添加的新书）之前，你还没有真正完成计数。这就是我们所说的**“尾递归”**。它就像从头开始一轮新的计数，但带有一些你已经收集到的额外信息。

尾递归的用途

尾递归主要用于几种计算。其中一些如下：

计算阶乘

如前所述，使用尾递归计算数字的阶乘是一个常见的例子。函数在每次**递归调用**时都会将数字乘以累加器。

计算指数

另一个例子是使用**尾递归**计算数字的幂。函数递归地将底数乘以自身，每次都减少指数，直到它变为**零**。

查找斐波那契数

使用尾递归**查找斐波那契数**是可能的。函数计算最后两个斐波那契数的和，并将它们作为参数传递给递归调用。

在排序数组中进行二分查找

使用尾递归实现**二分查找**是可行的。函数将目标元素与中间元素进行比较，并根据此通过递归调用在**左**或**右子数组**中执行查找。

反转列表

使用尾递归**反转列表**是可能的。函数获取第一个元素，并在每次递归调用中将其添加到反转子列表的末尾。

字符串反转

使用尾递归**反转字符串**也是可能的。函数获取字符串的第一个字符，并在每次递归调用中将其添加到反转子字符串的末尾。

计数列表元素

使用**尾递归**计数列表中元素的数量是另一个例子。函数为每个元素递增一个计数器，并使用列表的其余部分递归调用自身。

树遍历

在某些情况下，像**后序遍历**这样的**树遍历算法**可以使用尾递归实现。函数访问**左**和**右子树**，然后以**尾递归方式**处理当前节点。

生成排列

使用尾递归**生成集合的排列**是可能的。函数交换集合中的元素并递归生成剩余元素的排列。

生成组合

使用尾递归**生成元素的组合**也是可行的。函数通过包含或排除每个元素来递归生成组合。

C 语言中尾递归的示例

示例 1：使用尾递归打印数字的阶乘。

输出

说明

在此示例中，函数首先检查**“n”**的当前值是否为**0**。如果是，它就不再继续乘法；它只返回一直在累积的**“累加器”**。这是停止递归的基准情况。

如果**“n”**不为**0**，函数会计算**“n”**和**“累加器”**的乘积。之后，它会**新调用**自身，但使用较小的**“n”**值和新结果作为**“累加器”**。

这个过程一直持续，直到**“n”**变为**0**。每次函数调用自身时，都像是朝着解决问题迈出了一小步。递归调用作为函数中的最后一步发生，这被称为**尾递归**。

**尾递归**之所以智能，是因为它更有效地利用内存。计算机不需要记住很多东西，因为它只关注**当前步骤**和新结果。这样，它就像在做乘法的同时也在计数。

示例 2：使用尾递归打印斐波那契序列。

输出

说明

在此示例中，程序使用名为**“fibonacci”**的函数来查找**斐波那契序列**中的特定数字。此函数有三个数字作为输入：**“n”**（您要查找的数字的索引）、**“a”**（序列中的第一个数字）和**“b”**（序列中的第二个数字）。

在**“fibonacci”函数**内部，有一个条件检查**“n”**是否为**0**。如果是，则表示您已找到要查找的数字。因此，函数返回**“a”**的值。

如果**“n”**不为**0**，函数会计算**斐波那契序列**中的下一个数字。它可以通过再次调用自身，但采用不同的设置来完成此操作。**“a”**变为**“b”**（第二个数字），**“b”**变为**“a”**和**“b”**之和（第三个数字）。

这个过程一直重复，直到**“n”**变为**0**。每次**递归调用**时，您都在离找到您感兴趣的**斐波那契数**更近一步。

在代码的**“main”函数**中，您将**“n”**的值设置为**6**（这意味着您要查找**第 6 个斐波那契数**）。之后，您使用起始数字**0**和**1**调用**“fibonacci”函数**。

**“fibonacci”**函数的结果存储在**“result”变量**中，最后，您打印出**“n”**的值以及该索引处的**斐波那契数**。

简单来说，这段代码就像一场冒险，你一步步地遵循**斐波那契序列**，每一步都离找到你正在寻找的特定数字更近一步。此代码对于**“n = 6”**的结果将是斐波那契序列中的第 6 个数字，即**8**。

示例 3：打印组合

输出

说明

在此示例中，程序使用**“generateCombinations”函数**来创建这些组合。此函数需要一些东西才能工作：原始数字集合**（“arr”）**、可用数字的总数**（“n”）**、组合中的当前位置**（“index”）**、正在增长的组合本身**（“combination”）**、每个组合所需的大小**（“k”）**以及从何处开始选择数字**（“start”）**。

在**“generateCombinations”函数**内部，有一个检查以查看您是否已收集到足够的数字以构成完整组合。如果已收集到，则表示您已获得**完整集合**，因此您将这些数字打印出来，然后重新开始查找更多**组合**。

如果您尚未收集到足够的数字，函数将开始逐个选择数字。它从您上次停下的位置选择一个数字，并将其添加到**“combination”**中。之后，它会调用自身，但组合中会多一个数字，并为选择**下一个数字**设置一个新的起点。

这个过程一直持续，函数尝试不同的数字并创建不同的组合，直到它收集到足够的数字以构成**完整集合**。

在代码的**“main”函数**中，您有一个数字数组**（1、2、3 和 4）**，并且您想一次创建**2 个数字**的组合。之后，您设置一个名为**“combination”**的数组来存储每个组合，然后调用**“generateCombinations”函数**来启动该过程。

该函数使用提供的数字遍历所有可能的**大小为 2** 的组合并将其打印出来。

示例 4：使用尾递归打印排列

输出

说明

在此示例中，程序使用一个名为**“swap”**的函数，该函数可帮助您交换两个字符的位置。这就像更改**一副牌**中**两张牌**的位置。

之后，您还有另一个名为**“generatePermutations”**的函数。它接受一个字母字符串**（“str”）**、排列字母的起始位置**（“start”）**和结束位置**（“end”）**。

在**“generatePermutations”函数**内部，有一个检查以查看您是否已完成字母的重新排列。如果已完成，则表示您已创建新排列，因此将其打印出来。

如果您尚未完成，函数将开始交换字母。它取一个字母并将其与另一个字母交换。之后，它会调用自身，但使用下一个要排列的位置和相同的结束位置。

这个过程一直持续，**函数以各种方式交换和重新排列字母**，每次都创建新的排列。

遍历所有可能的排列后，会发生**“回溯”**。这意味着它撤销了上次交换，因此可以在下一轮排列中尝试不同的交换。

在**主函数**中，我们调用程序中存在的**generatePermutations**函数，以便该函数给出字母**A、B**和**C**的所有排列。

该函数遍历字母的所有可能排列并逐个打印出来。

示例 5：使用尾递归进行后序树遍历。

输出

说明

结构体 Node

此行定义了一个名为**“Node”**的新结构体。它包含两个指针，即左指针和右指针。这些表示给定树的左子节点和右子节点。在这种情况下，**“Node”**具有整数值**（“data”）**和两个指向其他**“Node”**的**“指针”**，分别名为**“left”**和**“right”**。

void postOrderTraversal(struct Node* root)

此行定义了一个名为**“postOrderTraversal”**的函数。它接受一个名为**“root”**的**“Node 指针”**作为输入。此函数可帮助您探索**“树”**（一种特殊的数据结构）的节点。它使用**“后序”方法**，这意味着它首先访问**左侧**，然后访问**右侧**，最后处理**当前节点**。

if (root == NULL) { return; }

此行检查当前节点（**“root”**节点）是否为空（NULL）。如果为空，则表示您已到达树的此分支的末尾，因此在此处停止。

postOrderTraversal(root->left); 和 postOrderTraversal(root->right);

这些行是奇迹发生的地方。函数调用自身两次，一次用于树的**左侧（“root->left”）**，一次用于**右侧（“root->right”）**。这样，您就可以使用递归探索整棵树。

printf("%d ", root->data);

此行打印当前节点的**“data”**。在此示例中，它是您存储在节点中的数字。由于是后序遍历，它在访问所有**左分支**和**右分支**后打印。

struct Node* createNode(int data)

这定义了一个名为**“createNode”**的函数。它接受一个整数值**“data”**作为输入，并返回一个具有此数据的新**“Node”**。此函数可帮助您为树创建新节点。

newNode->data = data;

此行将新创建节点的**“data”值**设置为给定的**“data”值**。

newNode->left = NULL; 和 newNode->right = NULL;

这些行将新节点的**左**和**右指针**设置为**NULL**。这意味着新节点尚未建立任何连接。

int main() {

这是您的程序开始执行的地方。它是程序的主要**“main”**函数。

struct Node* root = createNode(1);

此行创建一个**“Node”**，其**值为 1**，并将其存储在一个名为**“root”**的指针中。

root->left = createNode(2); 和 root->right = createNode(3);

这些行创建了另外两个值为**2**和**3**的节点，并将它们连接到**“root”**节点的**左侧**和**右侧**。

root->left->left = createNode(4); 和 root->left->right = createNode(5);

这些行创建了两个值为**4**和**5**的节点，并将它们连接到**“root”的左节点的左侧**。所以，这就像你在建造一棵小树。

printf("后序遍历： ");

此行只是**打印**一条消息，让您知道接下来会发生什么。

postOrderTraversal(root);

您以**“root”节点**为起点调用**“postOrderTraversal”函数**。此函数将以**后序方法**探索整棵树。