C 递归函数

在函数内部调用自身的函数称为递归函数。这种技术被称为递归。

递归原理

以下是递归函数调用的伪代码：

// 函数
void recurse()
{
    ... .. ...
    recurse();  // 调用函数本身
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

如果没有跳出条件，递归会一直嵌套执行下去。

为了防止无限递归，可以搭配使用 if…else 语句（或类似方法）。只有在满足条件的分支中进行递归调用，其他分支不递归。

示例：使用递归求和

以下示例使用递归求取 1 到用户输入的数的所有的自然数的总和。

#include <stdio.h>
int sum(int n);

int main() {
    int number, result;

    printf("Enter a positive integer: ");
    scanf("%d", &number);

    result = sum(number);

    printf("sum = %d", result);
    return 0;
}

int sum(int n) {
    if (n > 0)
        // sum() function calls itself
        return n + sum(n-1);
    else
        return n;
}

输出

Enter a positive integer: 3
sum = 6

我们写了一个 sum() 函数求取 1 到给定参数之间所有自然数的总和。 sum() 函数的实现逻辑是：

如果参数 n > 0，那么总和为 n + sum(n-1)。 n-1 为比 n 小 1 的自然数。
如果参数 n == 0，直接返回 n，也就是 0。

最初，从 main() 函数调用 sum(number)，将程序的控制权转到 sum 函数内部。

第 1 次是调用 sum(3) 时， n = 3。由于此时 n > 0，则返回 3 + sum(2)，由于 sum(2) 此时未知，需要计算，则运行时会将此结果暂存起来：sum(3) = 3 + sum(2)。
第 2 次是调用 sum(2) 时， n = 2。由于此时 n > 0，则返回 2 + sum(1)，由于 sum(2) 此时未知，需要计算，则运行时会将此结果暂存起来：sum(2) = 2 + sum(1)。
第 3 次是调用 sum(1) 时， n = 1。由于此时 n > 0，则返回 1 + sum(0)，由于 sum(0) 此时未知，需要计算，则运行时会将此结果暂存起来：sum(1) = 1 + sum(0)。
第 4 次是调用 sum(0) 时， n = 0。由于此时 n == 0，则返回 0，得出结果：sum(0) = 0。
然后根据 sum(0) = 0 逆向反推回去，得出：
- sum(1) = 1 + sum(0) = 1 + 0 = 1
- sum(2) = 2 + sum(1) = 2 + 1 = 3
- sum(3) = 3 + sum(2) = 3 + 3 = 6
这样，就得出了最终结果。

此示例的整个调用流程，也可参看下图：

递归的优缺点

递归使程序优雅，相比较于循环，能够大量简化代码。

但是，递归可能需要更多的性能开销。如果应用性能至关重要，改用循环是一个更好的办法。

递归是一个重要的概念。它经常用在数据结构和算法的案例中。例如，在树遍历等问题中使用递归是很常见的。

C 递归函数

递归原理

示例：使用递归求和

递归的优缺点

目录