深度剖析C语言函数递归（图文并茂）

函数递归是一种常用的编程技术，能够帮助解决一些复杂问题，如计算阶乘、生成斐波那契数列等。本节将讲解函数递归调用的原理和使用方法。

下面是一个函数递归的示例程序：

#include <stdio.h>
void func(int n)
{
    printf("%d\n", n);
    func(n + 1);
}

int main()
{
    func(0);
    return 0;
}

运行上述代码会发现，程序会不断输出数字，如 0、1、2、3 等，一直持续下去。这是因为在函数 func() 的实现中，它在自身内部调用了自身，这种调用被称为函数递归。

具体来说，在主函数 main() 中调用了 func() 函数，并将参数 0 传递给了 func() 函数。程序进入 func() 函数后，输出参数 n 的值为 0。接着，将 n + 1 作为 func() 函数的参数，该函数开始了一次自调用。由于 func() 函数中又调用了 func() 函数，因此函数将不断地自调用，形成了一个死循环。这类似于一条蛇咬住了自己的尾巴，将形成一个环形。调用过程如下图所示：


然而，由于没有设定任何终止递归的条件，函数将无限地递归下去，最终导致程序崩溃。如果程序陷入了循环，可使用快捷键 Ctrl + C 来终止程序。

正确的函数递归

在 C语言中，递归分为递推和回归两个阶段：

• 递推阶段是指递归函数从调用者开始不断地调用自身，处理子问题，直到达到基本情况，然后开始回归；
• 回归阶段是指递归函数在处理完基本情况后开始回溯，将每个子问题的结果合并以得出最终结果，并返回调用者。

因此，正确的递归实现必须处理好递推和回归两个阶段。

很显然，上面的实例并不是一个正确的递归实现，它只有一个递推规则，即每次将 n 加 1，但缺少一个递推结束条件，我们需要让程序能够正常结束并返回结果。

递归函数必须满足两个要素：递推规则和递推结束条件。只有同时满足这两个条件，递推阶段才是正确的。

现在我们给程序加上递推结束条件，当 n 为 5 时，结束递推。具体代码为：

#include <stdio.h>
void func(int n) // 定义递归函数 func
{
    if (n == 5)      // n 为 5 时，结束递推
        return;
    printf("%d\n", n);
    func(n + 1);
}

int main()
{
    func(0);
    return 0;
}

程序的运行结果为：

0
1
2
3
4

从运行结果不难看出，当 n 为 5 时结束递归。


上图用实线箭头展示了递推进入下级函数的流程，虚线箭头展示了从下级回归的流程。箭头方向和标号数字代表执行顺序。在 n 小于 5 之前，程序不断递推至下级函数；当 n 等于 5 时，程序开始回归。

通过添加递推结束条件，我们得到了一个正确的递归实现，能够正常结束并返回结果。

为了探究函数递归调用时的递推和回归过程，我们可以在 func() 函数前后分别加入 printf() 语句，具体代码如下：

#include <stdio.h>
void func(int n)
{
    if (n == 5)
        return;
    printf("after %d\n", n);    // 递推时执行
    func(n + 1);
    printf("before %d\n", n);   // 回归时执行
}

int main()
{
    func(0);
    return 0;
}

程序输出的结果为：

after 0
after 1
after 2
after 3
after 4
before 4
before 3
before 2
before 1
before 0

可以看到，程序先输出 5 个 after，值分别为 0、1、2、3、4。然后，程序输出 5 个 before，值分别为 4、3、2、1、0。

接下来，我们来仔细分析递推和回归的过程，如下图所示。


在图 3 中，实线箭头表示递推，虚线箭头表示回归。printf() 函数前的数字标号表示其执行的先后顺序。标号为 1、2、3、4、5 的 printf() 语句在递推过程中被依次执行，而标号为 6、7、8、9、10 的 printf() 语句则必须等到回归过程才会被执行。由于回归过程和递推过程是逆序的，因此输出的 n 值也是逆序的。

我们可以看出，在递归调用之前的语句将在递推过程中被执行，而在递归调用之后的语句则将在回归过程中被执行。

函数递归计算阶乘

接下来我们探讨如何使用递归来计算一个正整数的阶乘 n!。

阶乘是指所有小于或等于该数的正整数的乘积。对于 0，它的阶乘定义为 1，而对于负数，它没有阶乘。

例如：

4! = 4 * 3 * 2 * 1
3! = 3 * 2 * 1
2! = 2 * 1
1! = 1
0! = 1

根据这个规律，我们还能将阶乘这样计算：

4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1
0! = 1

可以使用以下递归规则来计算阶乘：

• 如果 n 为 1 或 0，则 n 的阶乘为 1；
• 如果 n 大于 1，则 n 的阶乘为 n * (n - 1)!。

假设有一个函数 f(n)，它接收一个整数 n 并返回 n 的阶乘 n!，那么该函数需要满足以下两个条件：

• 当 n 为 1 或 0 时，f(n) 返回 1；
• 当 n 大于 1 时，f(n) = n * f(n - 1)。

下面是具体的代码实现：

#include <stdio.h>
int f(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    return n * f(n - 1);
}

int main()
{
    int result = f(4);
    printf("%d\n", result);
    return 0;
}

在递归的过程中，函数每次调用时传入的参数 n 分别为 4、3、2、1。当 n 为 1 时，函数开始回归；回归到 n 为 2 时，计算 2 * 1；回归到 n 为 3 时，计算 3 * (2 * 1)；回归到 n 为 4 时，计算 4 * (3 * 2 * 1)，如下图所示。

函数递归计算斐波那契数列

斐波那契数列是一种数学序列，其中前两项为 1，之后的每一项是前两项的和。例如：

第 1 项：1
第 2 项：1
第 3 项：1 + 1 = 2
第 4 项：1 + 2 = 3
第 5 项：2 + 3 = 5
第 6 项：3 + 5 = 8

对于斐波那契数列，我们可以很容易地得出它的递推关系。如果有一个函数 f(n)，它的参数是一个整数 n，返回斐波那契数列的第 n 项，那么需要满足以下两个条件：

• 当 n 为 1 或 2 时，f(n) 返回 1；
• 当 n 大于 2 时，f(n) = f(n - 1) + f(n - 2)。

根据上述规律，我们可以编写出程序代码，如下所示：

#include <stdio.h>
int f(int n)
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    return f(n - 1) + f(n - 2);
}

int main()
{
    int result = f(4);
    printf("%d\n", result);
    return 0;
}

下图显示了斐波那契数列的流程。其中，实线箭头表示递归过程，虚线箭头表示回归过程。


当表达式 f(n - 1) + f(n - 2) 中的两个函数均回归结果时，可以计算和，再回归上级。