c语言递归算法例子

递归算法是一种在函数中调用自身的编程技术，它允许问题被分解成更小的子问题来解决。C语言中的递归算法非常强大，但也需要谨慎使用，因为不当的递归可能会导致栈溢出错误。

递归算法的基本概念

递归算法通常包含两个主要部分：基本情况（Base Case）和递归步骤（Recursive Step）。

• 基本情况：这是递归终止的条件，用于防止无限递归。
• 递归步骤：这是函数调用自身的地方，每次调用都应该更接近基本情况。

递归算法的实现要点

1. 明确递归终止条件：确保递归有一个明确的退出点。
2. 确保每次递归都接近基本情况：每次递归调用都应该使问题更小或更简单。
3. 避免重复计算：在可能的情况下，使用记忆化递归（也称为自顶向下的动态规划）来存储已经解决的子问题的答案，避免重复计算。

C语言递归算法示例

示例1：计算阶乘

阶乘函数是一个经典的递归示例。阶乘定义为n! = n * (n-1) * (n-2) * ... * 1，其中0! = 1。

#include 

int factorial(int n) {
    if (n == 0) { // 基本情况
        return 1;
    }
    return n * factorial(n - 1); // 递归步骤
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

示例2：斐波那契数列

斐波那契数列是一个每一项都是前两项和的序列，通常定义为F(0) = 0, F(1) = 1, 且对于n > 1, F(n) = F(n-1) F(n-2)。

#include 

int fibonacci(int n) {
    if (n <= 1) { // 基本情况
        return n;
    }
    return fibonacci(n - 1)   fibonacci(n - 2); // 递归步骤
}

int main() {
    int num = 10;
    printf("%dth Fibonacci number is %d\n", num, fibonacci(num));
    return 0;
}

示例3：二叉树遍历

二叉树的遍历是递归算法的另一个常见应用。以下是二叉树的先序遍历示例。

#include 
typedef struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

void preorderTraversal(TreeNode* node) {
    if (node == NULL) { // 基本情况
        return;
    }
    printf("%d ", node->value); // 访问当前节点
    preorderTraversal(node->left); // 递归遍历左子树
    preorderTraversal(node->right); // 递归遍历右子树
}

int main() {
    // 构建一个示例二叉树
    TreeNode root = {1, NULL, NULL};
    root.left = (TreeNode*)malloc(sizeof(TreeNode));
    root.left->value = 2;
    root.right = (TreeNode*)malloc(sizeof(TreeNode));
    root.right->value = 3;
    
    preorderTraversal(