1. （必做题）已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法和非递归算法：（1)求链表中的最大整数。（2)求所有整数的平均值。算法题C++

在C++中，我们可以使用递归和迭代的方式分别实现这两个操作。

**递归算法：**

1. **求最大整数**

// 递归寻找最大值
int findMaxRecursive(Node* f) {
    if (f == nullptr) return INT_MIN; // 空链表或第一个元素即为最小值
    int max = f->data;
    if (max < findMaxRecursive(f->next)) {
        max = findMaxRecursive(f->next);
    }
    return max;
}

2. **求平均值**

// 由于递归无法直接计算平均值，需要辅助变量记录总和
int sumAndFindAverageRecursive(Node* f, int& sum) {
    if (f == nullptr) return 0;
    sum += f->data;
    return sumAndFindAverageRecursive(f->next, sum) + f->data;
}

// 非递归版本求平均值
double findAverageRecursive(Node* f) {
    int total = sumAndFindAverageRecursive(f, 0);
    return (double)total / (f == nullptr ? 0 : 1);
}

**非递归算法：**

1. **求最大整数**

// 非递归寻找最大值
int findMaxNonRecursive(Node* f, Node* prev = nullptr) {
    if (f == nullptr) return prev->data;
    return f->data > prev->data ? f->data : findMaxNonRecursive(f->next, f);
}

2. **求平均值**

// 使用栈遍历求平均值
double findAverageNonRecursive(Node* f) {
    double sum = 0;
    Node* current = f;
    while (current != nullptr) {
        sum += current->data;
        current = current->next;
    }
    return sum / (f == nullptr ? 0 : 1);
}