C 中的尾递归

尾递归（tail recursion）是指递归函数中，递归调用是该函数的最后一条语句。在某些编程语言中，编译器或解释器可以对尾递归进行优化，将其转化为循环，从而减少函数调用的开销。

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

就像你堆放书籍时一样。假设您有一堆书，想要数一下有多少本书。为此，您一次数一本书并记录总数。当你数最后一本书时，你不是完成并大声说出总数，而是开始重新数一摞书，只在总数中添加一本书。

这样，直到您清点了所有书籍（包括刚刚添加的新书）后，您才真正完成了清点。这就是我们所说的“尾递归”。这就像从头开始新一轮的计数，但需要收集一些额外的信息。

尾递归的用途：
尾递归主要用在一些计算中。其中一些如下：

计算阶乘：
如前所述，使用尾递归计算数字的阶乘是一个常见的示例。该函数在每次递归调用时不断将数字与累加器相乘。

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

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

排序数组中的二分查找：
使用尾递归实现二分查找是可行的。该函数将目标元素与中间元素进行比较，并在此基础上通过递归调用在左子数组或右子数组中执行搜索。

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

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

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

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

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

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

C语言尾递归
在C语言中，尾递归的优化并非由语言标准要求，而是由编译器的实现决定。通常来说，许多现代的编译器会对尾递归进行优化，将其转化为迭代形式，以减少栈的深度，提高程序的性能。

include <stdio.h>

int factorial(int n, int result) {
    if (n == 0 || n == 1) {
        return result;
    } else {
        return factorial(n - 1, n * result);
    }
}

int main() {
    int n = 5;
    int result = factorial(n, 1);
    printf("Factorial of %d is %d\n", n, result);

    return 0;
}

在上述例子中，factorial 函数是一个计算阶乘的递归函数，而且是尾递归。编译器可以通过优化将其转化为等效的迭代形式，以提高性能。

需要注意的是，并非所有的递归函数都能被优化为尾递归形式，具体情况取决于编译器的实现。

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

include <stdio.h>  
int fibonacci(int n, int a, int b) {  
    if (n == 0) {  
        return a;  
    } else {  
        return fibonacci(n - 1, b, a + b);  
    }  
}  
int main() {  
    int n = 6;  
    int result = fibonacci(n, 0, 1);  
printf("Fibonacci number at index %u is %u\n", n, result);  
    return 0;  
}  

在 "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：使用尾递归的后序树遍历。

include <stdio.h>  
include <stdlib.h>  
struct Node {  
    int data;  
    struct Node* left;  
    struct Node* right;  
};  
void postOrderTraversal(struct Node* root) {  
    if (root == NULL) {  
        return;  
    }  
  
postOrderTraversal(root->left);  
postOrderTraversal(root->right);  
printf("%d ", root->data);  
}  
struct Node* createNode(int data) {  
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  
newNode->data = data;  
newNode->left = NULL;  
newNode->right = NULL;  
    return newNode;  
}  
int main() {  
    struct Node* root = createNode(1);  
    root->left = createNode(2);  
    root->right = createNode(3);  
    root->left->left = createNode(4);  
    root->left->right = createNode(5);  
printf("Post-order traversal: ");  
postOrderTraversal(root);  
    return 0;  
}  

这一行定义了一个名为 "节点 "的新结构。它包含两个指针，即左指针和右指针。它们分别代表所给树的左子树和右子树。在这种情况下，一个 "节点 "有一个整数值（"数据"）和两个指向其他 "节点 "的 "指针"，分别称为 "左 "和 "右"。

void postOrderTraversal(struct Node* root)：

这一行定义了一个名为 "postOrderTraversal "的函数。它将名为 "root "的 "节点 "指针作为输入。该函数可以帮助你探索 "树"（一种特殊的结构）的节点。它使用 "后序 "方法，即首先向左，然后向右，最后处理当前节点。

if (root == NULL) { return; }：

这一行检查当前节点（"根 "节点）是否为空（NULL）。如果为空，则表示已到达树的这一分支的末尾，因此到此为止。

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

这两行是神奇之处。函数会调用自身两次，一次是针对树的左侧（"root->left"），另一次是针对树的右侧（"root->right"）。这样，你就可以用递归的方式探索整棵树。

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

这一行打印当前节点的 "数据"。在示例中，它是你存储在节点中的数字。由于是后序遍历，所以是在访问了所有左右分支后打印的。

struct Node* createNode(int data)：

该函数定义了一个名为 "createNode "的函数。它将一个整数值 "data "作为输入，并返回一个具有该数据的新 "节点"。该函数可帮助您为树创建新节点。

newNode->data = data;：

这一行将新创建节点的 "data "值设置为给定的 "data "值。

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

这两行将新节点的左指针和右指针设置为 NULL。这意味着新节点还没有任何连接。

int main() {：

这是程序开始执行的地方。这是程序的 "主 "函数。

struct Node* root = createNode(1);：

这一行创建了一个值为 1 的新 "节点"，并将其存储在一个名为 "root "的指针中。

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

这两行将创建另外两个节点，节点值分别为 2 和 3，并将它们连接到 "根 "节点的左右两边。

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

这两行分别创建了值为 4 和 5 的两个节点，并将它们连接到 "根 "左节点的左侧。因此，这就像是在构建一棵小树。

printf("Post-order traversal: ");：

这一行只是打印一条信息，让你知道接下来会发生什么。

postOrderTraversal(root);：

以 "根 "节点为起点，调用 "postOrderTraversal "函数。该函数将以后序方法遍历整棵树。