C 递归函数 - 绿叶网

C 递归函数简介

在 C 语言中，递归函数指的是一个函数内部会自己调用自己。递归函数可以用于解决具有重复性特征的问题，比如计算阶乘、斐波那契数列等。

如果一个函数在内部直接调用自己，称为 “直接递归”。如果一个函数在内部的下层函数中再去调用自己，称为 “间接递归”。一般情况下，我们采用的都是直接递归。

示例 1：递归函数计算 1 + 2 + ... + 100 的和

#include <stdio.h>

int sum(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    return n + sum(n - 1);
}

int main(void)
{
    printf("%d", sum(100));
    return 0;
}

运行结果如下。

分析：

在这个例子中，我们定义了一个 sum() 函数用于计算 1 + 2 + … + n 的和，它满足下面的递归关系。这种递归关系，表示的是 1 ~ n 的和可以由 n 加上 1 ~ n - 1 的和计算得到。如果 n 是 1，可以直接得到结果。

求和公式

需要特别注意的是，递归函数一定要有一个退出条件（也称为基本情况或终止条件），否则就会一直递归下去，导致 “栈溢出（stack overflow）” 。对于上面这个例子来说，它的退出条件就是 n <= 1。当 n 最终减小到 1 时，递归停止，函数开始逐层返回结果。

C 递归函数实现 “斐波那契数列”

斐波那契数列，又称 “黄金分割数列” 或 “兔子数列”，它指的是这样一个数列：0、1、1、2、3、5、8、13、21、34……。对于斐波那契数列，它从第 3 项开始，每一项都等于前两项之和，所以满足下面的公式。

斐波那契数列公式

接下来我们尝试使用递归函数的方式来求出斐波那契数列前 20 项数字是什么（从 0 项开始）。

示例 2：递归函数实现斐波那契数列

运行代码

#include <stdio.h>

int fibonacci(int n)
{
    if (n < 2)
    {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

int main(void)
{
    for (int i = 0; i <= 20; i++)
    {
        printf("%d, ", fibonacci(i));
    }
    return 0;
}

运行结果如下。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,

分析：

在这个例子中，我们定义了一个 fibonacci() 函数，该函数是一个递归函数。对于 fibonacci() 来说，它递归的退出条件为 n < 2。

C 递归函数的优缺点

在 C 语言中，对于递归函数来说，它有以下的优点。

代码简洁：对于某些问题，递归实现的代码往往比迭代实现的代码更加简洁易懂，更符合问题的自然描述。
可读性高：递归的逻辑通常更容易理解，尤其是在解决具有自相似结构的问题时。

同时，递归函数也有以下的缺点。

性能开销大：每次递归调用都需要在内存中分配新的栈帧，用于存储局部变量和返回地址等信息。如果递归深度过大，可能会导致栈溢出，程序崩溃。
效率可能较低：对于某些问题，递归可能会进行大量的重复计算，导致效率低下。例如，计算斐波那契数列的递归实现就存在很多重复计算。

此外，在使用递归函数时，小伙伴们要注意以下几点。

必须要有明确的退出条件：每个递归函数都必须定义一个或多个退出条件，确保递归能够最终停止，避免无限递归。
递归深度不宜过大：要注意控制递归的深度，避免栈溢出。对于可能导致深层递归的问题，可以考虑使用迭代等其他方法来解决。
考虑效率问题：对于性能敏感的应用，需要仔细评估递归的效率，并考虑是否可以使用更高效的迭代或其他算法来替代递归。