C语言教程-详情C语言中的递归思想

C语言中的递归

递归是一个函数调用自身以处理一个更小问题的过程。任何调用自身的函数称为递归函数，这样的函数调用称为递归调用。递归涉及多次递归调用，但重要的是要设置递归的终止条件。递归代码比迭代代码更短，但更难理解。

并非所有问题都适合使用递归，但对于可以用类似子任务来定义的任务，它更加有用。例如，递归可用于排序、搜索和遍历问题。

通常情况下，迭代解决方案比递归更高效，因为函数调用始终带来开销。任何可以通过递归解决的问题也可以通过迭代解决。然而，对于某些问题，递归是最佳选择，例如汉诺塔问题、斐波那契数列、阶乘计算等。

下面的例子使用递归计算一个数的阶乘。

#include <stdio.h>int fact(int n);
int main() {
    int n, f;
    printf("Enter the number whose factorial you want to calculate? ");
    scanf("%d", &n);
    f = fact(n);
    printf("factorial = %d", f);
    return 0;
}
int fact(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return n * fact(n - 1);
    }
}

输出结果：

Enter the number whose factorial you want to calculate? 5factorial = 120

递归函数

递归函数通过将任务分解为子任务来执行任务。在函数中定义了一个终止条件，满足该条件的某个特定子任务后，递归停止并从函数返回最终结果。

函数不再递归的情况被称为基本情况，而函数继续调用自身执行子任务的情况称为递归情况。所有递归函数都可以使用这种格式编写。

编写任何递归函数的伪代码如下所示。

if (测试基本情况) {
    return 一些值;
} else if (测试另一个基本情况) {
    return 另一些值;
} else {
    // 语句;   递归调用;}

C中递归的例子

我们来看一个例子，找出斐波那契数列的第n个项。

#include <stdio.h>int fibonacci(int n);
void main() {
    int n, f;
    printf("Enter the value of n? ");
    scanf("%d", &n);
    f = fibonacci(n);
    printf("%d", f);
}
int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

输出结果：

Enter the value of n? 12144

递归方法的内存分配

每次递归调用都会在内存中创建该方法的新副本。一旦某个数据由方法返回，副本就会从内存中删除。由于在函数内声明的所有变量和其他内容都存储在堆栈中，因此每次递归调用都会维护一个单独的堆栈。一旦从相应的函数返回了值，堆栈就会被销毁。递归涉及在每次递归调用中解决和跟踪值的复杂性。因此，我们需要维护堆栈并跟踪堆栈中定义的变量的值。

让我们考虑以下示例，以了解递归函数的内存分配。

int display(int n) {
    if (n == 0) {
        return 0;// 终止条件
    }else{
    printf("%d", n);
    return display(n - 1); // 递归调用
  }
}

说明：

让我们以n = 4为例，检查这个递归函数。首先，维护所有的堆栈来打印相应的n值，直到n变为0。一旦达到终止条件，堆栈就会依次返回0到其调用堆栈。有关递归函数的堆栈跟踪的更多信息。