【C语言】递归

一、什么是递归

递归是函数在其内部调用自己，其下次计算使用上次计算的结果，并且计算公式相同。递归函数可以拆除成两个主要部分：

• 结束条件：确定什么情况下停止递归。
• 递归步骤：分解后的最小的相同问题，即相同的计算公式。

二、递归的基本结构

递归的基本结构就是前文讲的两个主要部分。

2.1、结束条件

- 防止无限递归，需要有递归停止的条件。
- 一般是直接返回结果，通常返回1个值。

2.2、递归步骤

- 这是将问题拆分成最小的子问题，每1步返回1个值。
- 函数反复调用自身来计算最小的子问题。

3、递归示例

3.1、计算阶乘

计算n!是递归的经典案例。

int factorial(int n) {
    if (n == 0) { // 结束条件
        return 1;
    } else {
        return n * factorial(n - 1); // 递归步骤
    }
}

假设n=2，factorial被调用3次，内部调用2次。

3.1.1、调用

• 第1次–外部调用

• factorial(2);

• 内部第1次调用

• 2 * factorial(1)；

• 内部第2次调用

• 1 * factorial(0);

3.1.2、返回

• 内部第2次调用返回结果：1 = 1
• 内部第1次调用返回结果：1 = 1 * 1
• 外部调用返回结果：2 = 2 * 1 * 1

3.2、斐波那契数列

斐波那契数列的递归计算如下。

int fibonacci(int n) {
    if (n <= 1) { // 结束条件
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // 递归步骤
    }
}

四、 递归的特性

4.1、递归深度

• 每次递归调用都会在调用栈上分配新的空间。如果递归深度过大，可能会导致栈溢出。

4.2、性能问题：

• 递归可能导致性能问题，因为每次递归调用都需要保存上下文和栈帧。对于某些问题，迭代（循环）可能更高效。

4.3、尾递归优化：

• 某些编译器能够优化尾递归（即递归调用是函数中的最后一个操作），从而减少栈空间的使用。但这种优化在 C 语言中并不是所有编译器都支持。

五、递归的应用场景

• 树结构的遍历：例如中序遍历、前序遍历、后序遍历。
• 图的深度优先搜索：用于寻找路径或遍历图中的节点。
• 分治算法：如快速排序、归并排序等，通过递归将问题分解为更小的子问题。

六、递归的注意事项

• 结束条件：必须确保有明确的基准条件，否则递归将无法终止。
• 递归深度控制：尽量避免过深的递归调用，如果可能，考虑使用循环来代替递归。
• 资源管理：递归调用会消耗更多的栈空间，要注意避免不必要的资源浪费。

七、简单示列代码

一些常见的递归示例： 计算阶乘 斐波那契数列 递归遍历树结构。