C语言中函数的递归

在C语言中，递归是一种解决问题的方法，其中函数直接或间接地调用自身来解决问题。递归通常用于解决那些可以分解为更小、更简单的同类问题的问题。递归有两个关键部分：基本情况（base case）和递归情况（recursive case）。基本情况是递归停止的条件，而递归情况是函数调用自身的条件。

 

下面是一个使用递归实现的经典例子：计算阶乘（factorial）。

 

 

#include <stdio.h>

 

// 递归函数，计算阶乘

unsigned long long factorial(int n) {

    // 基本情况：0的阶乘是1

    if (n == 0) {

        return 1;

    }

    // 递归情况：n的阶乘等于n乘以(n-1)的阶乘

    else {

        return n * factorial(n - 1);

    }

}

 

int main() {

    int number;

    printf("Enter a number: ");

    scanf("%d", &number);

 

    // 计算并打印阶乘

    unsigned long long result = factorial(number);

    printf("Factorial of %d is %llu\n", number, result);

 

    return 0;

}

在这个例子中，factorial函数接受一个整数n作为参数，并返回n的阶乘。如果n是0，函数返回1（基本情况）。否则，函数返回n乘以(n-1)的阶乘（递归情况）。这个过程会一直重复，直到达到基本情况为止。

 

递归需要小心处理，因为它可能导致栈溢出，特别是当递归层次过深时。此外，递归函数通常比非递归函数更难理解和调试。

 

另一个递归的例子是斐波那契数列（Fibonacci sequence）：

 

#include <stdio.h>

 

// 递归函数，计算斐波那契数列的第n项

int fibonacci(int n) {

    // 基本情况

    if (n <= 1) {

        return n;

    }

    // 递归情况

    else {

        return fibonacci(n - 1) + fibonacci(n - 2);

    }

}

 

int main() {

    int n;

    printf("Enter a positive integer: ");

    scanf("%d", &n);

 

    // 计算并打印斐波那契数列的第n项

    printf("Fibonacci of %d is %d\n", n, fibonacci(n));

 

    return 0;

}

在这个例子中，fibonacci函数计算斐波那契数列的第n项。如果n是0或1，函数返回n（基本情况）。否则，函数返回第(n-1)项和第(n-2)项的和（递归情况）。注意，这个递归实现效率不高，因为它会重复计算很多相同的子问题。在实际应用中，通常会使用其他方法（如动态规划）来优化斐波那契数列的计算。