2.用递归函数求Fibonacci数列的第n项的值，并统计计算第n项所需的递归调用次数。C语言

在C语言中，你可以使用递归函数来求解斐波那契数列的第n项。斐波那契数列是一个每个数字等于前两个数字之和的序列，通常开始两项为0和1。以下是递归函数的基本实现：

#include <stdio.h>

// 定义递归函数 fib(n) 返回第 n 项的斐波那契数值
int fib(int n) {
    // 递归基本条件：当 n 为 0 或 1 时，直接返回相应数值
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;

    // 递归计算第 n 项，通过调用 fib 函数计算前两项的和
    int fib_n = fib(n - 1) + fib(n - 2);
    return fib_n;
}

// 计算并打印第 n 项的值及其所需递归调用次数
void calculate(int n) {
    int result = fib(n);
    printf("The %dth Fibonacci number is: %d\n", n, result);

    // 使用动态规划辅助变量记录递归调用次数
    int call_count = 0;
    for (int i = n; i >= 0; i--) {
        if (fib(i) != fib_cache[i])
            call_count++;
        fib_cache[i] = fib(i); // 将计算结果缓存到数组中防止重复计算
    }
    printf("Recursive calls needed to compute the %dth number: %d\n", n, call_count);
}

int main() {
    int n = 10; // 你想计算的项，可以根据需要修改
    calculate(n);
    return 0;
}

在这个代码中，`fib()`函数用于计算斐波那契数，`calculate()`函数则同时计算数值和递归调用次数。为了减少重复计算，我们使用了一个数组`fib_cache[]`来存储已经计算过的值。