使用代码实现斐波那契数列 （2）使用递归解决二叉树的深度问题。设计一个函数，计算二叉树的最大深度。最大深度是从根节点到最远叶子节点的最长路径上的节点数量。 （3）给定一个单链表的头节点 head，请使用递归的方式反转这个链表，并返回新的头节点 用c语言

（1）使用C语言实现斐波那契数列，我们可以采用递归的方式：

#include <stdio.h>

// 递归函数计算斐波那契数列
int fibonacci(int n) {
    if (n <= 1) // 基线条件：F(0) = 0 和 F(1) = 1
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
}

int main() {
    int n, i;
    printf("请输入一个非负整数: ");
    scanf("%d", &n);
    printf("斐波那契数列的第 %d 项是: %d\n", n, fibonacci(n));
    return 0;
}

当你运行此程序并输入一个数字时，会得到相应位置的斐波那契数值。

（2）计算二叉树的最大深度，同样采用递归：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int maxDepth(struct TreeNode* root) {
    if (root == NULL) // 基线条件：空树的深度为0
        return 0;
    else
        return 1 + MAX(maxDepth(root->left), maxDepth(root->right)); // 递归，取左右子树深度较大者加1
}

// 注意这里MAX是一个全局的或者局部的函数，用于返回两个整数中的较大值

（3）反转单链表（头插法）的递归版本：

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) // 基线条件：空链表或只有一个元素的链表
        return head;
    
    // 递归部分，先将当前节点的next指向下一段链表，然后更新头节点指向当前节点
    struct ListNode* newHead = reverseList(head->next);
    head->next->next = head; // 将原头节点作为新链表的尾巴
    head->next = NULL; // 更新原头节点的next指针
    
    return newHead; // 返回新头节点
}

当调用`reverseList(head)`时，会返回反转后的链表的新头部。