C 递归

C 语言 - 递归

递归（Recursion）是一种编程技术，指函数直接或间接调用自身来解决问题。它将问题分解为更小、与原问题相似的子问题，直到达到一个可以直接解决的简单基本情况（base case）。

一个递归函数通常有两个主要部分：

• 基本情况 (Base Case)： 一个或多个终止递归的条件。当满足基本情况时，函数直接返回一个值，不再进行递归调用。这是防止无限循环的关键。
• 递归步骤 (Recursive Step)： 函数通过修改参数调用自身的部分，使问题更接近基本情况。递归调用的结果通常用于计算当前调用的结果。

概念示例：

void recursive_function(parameters) {
    if (base_case_is_met) {
        // Solve the simplest case directly
        // 直接解决最简单的情况
        return base_case_value;
    } else {
        // Recursive step: Call itself with modified parameters
        // 递归步骤：用修改后的参数调用自身
        // Process the result of the recursive call
        // 处理递归调用的结果
        // Return the final result for this step
        // 返回此步骤的最终结果
        return recursive_call_result_processed;
    }
}

虽然 C 语言支持递归，但你必须确保存在一个基本情况，并且最终能够达到；否则，程序很可能会耗尽栈内存（Stack Overflow，栈溢出）并崩溃。

对于具有自然递归结构的问题，如遍历树形结构或解决某些数学问题，递归通常是一种优雅的解决方案。

示例 1：计算阶乘

非负整数 n 的阶乘（记作 n!）是所有小于或等于 n 的正整数的乘积。规定 0! = 1。

#include <stdio.h>
#include <stdlib.h> // For EXIT_SUCCESS

// Use unsigned long long to handle larger factorial values
// Factorials grow very quickly!
// 使用 unsigned long long 来处理更大的阶乘值
// 阶乘值增长非常快！
unsigned long long factorial(unsigned int n) {
    // Base case: factorial of 0 is 1
    // 基本情况：0 的阶乘是 1
    if (n == 0) {
        return 1;
    }
    // Recursive step: n * factorial(n-1)
    // 递归步骤：n * factorial(n-1)
    else {
        // Check for potential overflow before multiplication, though tricky.
        // A full check is complex. For large n, this might still overflow.
        // 在乘法前检查潜在的溢出，虽然这很棘手。
        // 进行全面的检查很复杂。对于较大的 n，这仍然可能溢出。
        return (unsigned long long)n * factorial(n - 1);
    }
}

int main(void) {
    unsigned int num = 15;
    // Note: factorial(15) fits in unsigned long long, but factorial(21) would overflow.
    // 注意：factorial(15) 适合 unsigned long long，但 factorial(21) 会溢出。

    printf("Factorial of %u is %llu\n", num, factorial(num));
    // Use %u for unsigned int, %llu for unsigned long long
    // 对于 unsigned int 使用 %u，对于 unsigned long long 使用 %llu

    return EXIT_SUCCESS;
}

编译并执行后，输出如下：

Factorial of 15 is 1307674368000

示例 2：斐波那契数列

斐波那契数列（Fibonacci sequence）始于 0 和 1。序列中后续的每一个数字都是前两个数字之和（0, 1, 1, 2, 3, 5, 8…）。

#include <stdio.h>
#include <stdlib.h> // For EXIT_SUCCESS

// Calculates the nth Fibonacci number (using recursion)
// 计算第 n 个斐波那契数（使用递归）
unsigned long long fibonacci(unsigned int n) {
    // Base cases
    // 基本情况
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    // Recursive step
    // 递归步骤
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(void) {
    int i;
    int limit = 10; // Calculate first 10 Fibonacci numbers (0 to 9)
    // 计算前 10 个斐波那契数（0 到 9）

    printf("First %d Fibonacci numbers:\n", limit);
    for (i = 0; i < limit; i++) {
        // Print the number, followed by a space
        // The original tutorial's %n format specifier was incorrect and dangerous.
        // 打印数字，后跟一个空格
        // 原始教程的 %n 格式说明符是不正确且危险的。
        printf("%llu ", fibonacci(i));
    }
    printf("\n");

    return EXIT_SUCCESS;
}

编译并执行后，输出如下：

First 10 Fibonacci numbers:
0 1 1 2 3 5 8 13 21 34

性能警告：

虽然递归的斐波那契数列解法很优雅，但它效率极低。它会多次重复计算相同的斐波那契数，导致时间复杂度呈指数级增长（大约 O(2^n)）。计算 fibonacci(40) 可能需要相当长的时间。

对于实际应用，迭代解法（使用循环）或**记忆化（memoization）/动态规划（dynamic programming）**技术在计算斐波那契数时要优越得多。

递归 vs. 迭代

每个递归问题都可以使用循环（如 for 或 while）通过迭代（Iteration）来解决。

• 递归： 对于具有自相似结构的问题可能更直观。通常能写出更短、更易读的代码（对于某些问题）。由于嵌套函数调用，可能会消耗大量的栈空间，深度递归有栈溢出的风险。由于函数调用开销和重复计算（如朴素的斐波那契示例），效率可能较低。
• 迭代： 在速度和内存使用方面通常更高效（使用堆内存或固定的栈空间，而不是不断增长的调用栈）。对于复杂的递归结构，有时可能更难概念化或编写。避免了与深度递归相关的栈溢出风险。

当递归能显著简化逻辑且递归深度预计可控时，选择递归。否则，为了更好的性能和内存安全，优先选择迭代。