C 递归

C 递归的完整使用攻略

什么是递归

递归是一种常用的编程技巧，它使程序能够对自身进行调用。在递归函数中，函数会不断调用自身，并在每次调用中传递不同的参数，从而使函数能够对复杂的问题进行处理。

递归函数的特点

• 递归函数必须有一个基本情况，即结束递归的条件，否则会无限循环下去。
• 每次递归都会使问题规模缩小，直到达到基本情况为止。
• 递归函数需要调用自身，直到达到基本情况为止。

如何使用递归

使用递归一般需要以下步骤：

1. 确定基本情况，即结束递归的条件。
2. 确定递归的规模变化，即每次递归问题的规模如何缩小。
3. 调用递归函数。

下面通过两个示例来详细讲解如何使用递归。

示例一：计算阶乘

阶乘是一个自然数与小于它的自然数的乘积，例如，4的阶乘是4x3x2x1=24。计算阶乘是一道经典的递归问题。

#include <stdio.h>

int factorial(int n);

int main() {
    int n;
    printf("请输入一个非负整数：");
    scanf("%d", &n);
    printf("%d 的阶乘是 %d\n", n, factorial(n));
    return 0;
}

int factorial(int n) {
    if (n == 0) {  // 基本情况：0的阶乘为1
        return 1;
    } else {  // 递归规模变化：每次将n-1作为函数参数调用自身
        return n * factorial(n-1);
    }
}

上面的程序中，factorial 函数通过递归的方式来计算阶乘。在函数中，我们首先定义了基本情况，即0的阶乘为1，然后定义了递归的规模变化，即每次将n-1作为函数参数调用自身。最后，在 main 函数中调用 factorial 函数计算阶乘。

示例二：计算斐波那契数列

斐波那契数列是指前两个数为1，从第三项开始，每个数都等于前两个数之和。因此，斐波那契数列的前10个数是1,1,2,3,5,8,13,21,34,55。

#include <stdio.h>

int fibonacci(int n);

int main() {
    int n;
    printf("请输入一个正整数：");
    scanf("%d", &n);
    printf("%d 的斐波那契数列值是 %d\n", n, fibonacci(n));
    return 0;
}

int fibonacci(int n) {
    if (n <= 2) {  // 基本情况：斐波那契数列的前两项为1
        return 1;
    } else {  // 递归规模变化：每次将n-1和n-2作为函数参数调用自身
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

上面的程序中，fibonacci 函数通过递归的方式来计算斐波那契数列的第n项。在函数中，我们首先定义了基本情况，即斐波那契数列的前两项为1，然后定义了递归的规模变化，即每次将n-1和n-2作为函数参数调用自身。最后，在 main 函数中调用 fibonacci 函数计算斐波那契数列的第n项。

总结

本文介绍了如何使用递归来解决问题，并通过两个示例讲解了递归函数的特点和如何使用递归来计算阶乘和斐波那契数列。在编写递归函数时，需要注意定义基本情况和确定递归规模变化。如果使用得当，递归可以使程序更加简洁和高效。