递归函数经典案例

递归函数是编程中一种非常强大且常见的技术，它允许函数调用自身来解决问题。递归在解决某些类型的问题时非常有效，尤其是那些可以被分解为相似子问题的问题。以下是一些经典的递归函数案例，它们展示了递归在实际编程中的应用。

1. 阶乘计算

阶乘函数是一个经典的递归案例。阶乘定义为 n! = n * (n-1) * (n-2) * ... * 1，递归公式可以表示为 n! = n * (n-1)!，其中基本情况是 1! = 1。

int factorial(int n) {
    if (n == 1) // 递归基本情况
        return 1;
    else
        return n * factorial(n - 1); // 递归调用
}

2. Fibonacci数列

Fibonacci数列是一个每一项都是前两项和的数列，通常定义为 F(0) = 0, F(1) = 1，且对于 n > 1，有 F(n) = F(n-1) F(n-2)。这是一个天然的递归问题。

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

3. 汉诺塔

汉诺塔问题是一个经典的递归问题，涉及将一堆大小不一的盘子从一个柱子移动到另一个柱子，过程中需要遵循特定规则。解决这个问题的递归策略是将问题分解为移动较小的盘子和移动最大的盘子。

void hanoi(int n, char source, char auxiliary, char target) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, target);
        return;
    }
    hanoi(n - 1, source, target, auxiliary); // 递归调用：将n-1个盘子移动到辅助柱
    printf("Move disk %d from %c to %c\n", n, source, target); // 移动最大的盘子
    hanoi(n - 1, auxiliary, source, target); // 递归调用：将n-1个盘子从辅助柱移动到目标柱
}

4. 二叉树遍历

二叉树的遍历是递归的另一个经典应用。无论是前序、中序还是后序遍历，都可以使用递归实现。

// 假设有二叉树节点结构体定义和二叉树的根节点root
void preorderTraversal(TreeNode* root) {
    if (root != NULL) {
        visit(root); // 访问当前节点
        preorderTraversal(root->left); // 递归遍历左子树
        preorderTraversal(root->right); // 递归遍历右子树
    }
}

5. 爬楼梯问题

这个问题描述了一个人爬楼梯，可以一步走一级或两级台阶。求走到第n级台阶的方法数。这同样可以用递归来解决，因为走到第n级台阶的方法数等于走到第n-1级和第n-2级台阶的方法数之和。

int climbStairs(int n) {
    if (n <= 2) // 递归基本情况
        return n;
    else
        return climbStairs(n - 1)   climbStairs(n - 2); // 递归调用
}

递归函数的强大之处在于其简洁性和对问题的直接表达能力。然而，递归也可能导致性能问题，如栈溢出和重复计算。在实际应用中，有时需要结合动态规划或其他技术来优化递归算法，以避免这些问题。