递归+动态链表实现n>50的斐波那契数列优化求助

我正在完成算法课程作业，需要实现一个程序：输入n>50的整数，输出斐波那契数列的第n项。要求必须使用递归和动态结构（链表），且只能用标准库（不能用矩阵、容器、vector等）。

我写的C++代码仅支持n<34的情况，满足不了n>50的需求。想通过缓存已计算的斐波那契值来优化，但不知道怎么在保持递归特性的同时实现缓存，也不确定是否必须用类来实现，希望得到优化方向的指导，帮我完成学习并通过考试。

#include <iostream>
#include <fstream>

using namespace std;

class List
{
public:
    struct Node{
        int position;
        int value;
        Node *next;

        Node(int x, int y) : value(x), position(y), next(nullptr){};
    };

    Node *head;

    List() : head(nullptr) {}

    void printList(){
        Node *current = head;
        while (current){
            cout << "Pozice: " << current->position << ", Hodnota: " << current->value << endl;
            current = current->next;
        }
    }

    void addNode(int value, int position){
        Node *newNode = new Node(value, position);

        if (head == nullptr){
            head = newNode;
        }
        else{
            Node *current = head;
            while (current->next != nullptr){
                current = current->next;
            }
            current->next = newNode;
        }
    }

    void deleteList() {
        while (head != nullptr) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    void saveFile(){
        ofstream myFile("output.txt");

        Node *current = head;
        
        while (current->next != nullptr){
            current = current->next;
        }

        myFile << "Pozice: " << current->position << ", Hodnota: " << current->value << endl;

        myFile.close();
        cout << "Výsledky byly v pořádku uloženy!" << endl;
    }
};
int fibonacci(int n){
    List *list = new List();
    if (n <= 1){
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

List *createList(int n){
    List *list = new List();

    if (n <= 0){
        return list;
    }

    for (int i = 1; i <= n; ++i){
        list->addNode(fibonacci(i), i);
    }

    return list;
}

int main(){
    int n = 33;
    List *fibonacci = createList(n);

    fibonacci->printList();

    fibonacci->saveFile();
    fibonacci->deleteList();
    return 0;
}

1. 修复核心问题：用链表做共享缓存，而非每次递归新建链表 #

你现在的fibonacci函数每次递归都新建一个List，完全没用到缓存的作用。正确的做法是共用同一个链表缓存：递归前先检查缓存里有没有当前n的斐波那契值，有就直接返回；没有就递归计算n-1和n-2，求和后把结果存入缓存，再返回。

2. 解决整数溢出问题 #

n>46时，斐波那契数会超过int的最大值（2^31-1=2147483647），比如F(47)=2971215073，直接用int会溢出导致错误。必须把链表节点里的value类型改成long long，同时递归函数的返回值也换成long long。

3. 改造递归函数与链表交互 #

修改后的递归函数需要接收缓存链表的指针，实现"查缓存→递归计算→存缓存"的逻辑：

long long fibonacci(int n, List* cache) {
    // 先遍历缓存查找是否已计算过n项
    List::Node* current = cache->head;
    while (current != nullptr) {
        if (current->position == n) {
            return current->value;
        }
        current = current->next;
    }

    // 未找到则递归计算
    long long result;
    if (n <= 1) {
        result = n;
    } else {
        result = fibonacci(n-1, cache) + fibonacci(n-2, cache);
    }

    // 将结果存入缓存
    cache->addNode(result, n);
    return result;
}

4. 调整链表类适配long long #

把List类中Node的value成员类型改成long long，同时addNode函数的参数类型也对应修改：

struct Node{
    int position;
    long long value;  // 改为long long
    Node *next;

    Node(long long x, int y) : value(x), position(y), next(nullptr){};
};

void addNode(long long value, int position){  // 参数类型同步修改
    Node *newNode = new Node(value, position);
    // 原尾插逻辑不变
}

5. 简化主流程逻辑 #

不需要再用createList循环调用fibonacci，直接在main里创建缓存链表，调用一次递归就能得到第n项，同时缓存会自动填充所有依赖的项：

int main(){
    int n = 55;  // 支持n>50
    List* cache = new List();

    long long result = fibonacci(n, cache);
    cout << "Pozice: " << n << ", Hodnota: " << result << endl;

    cache->saveFile();
    cache->deleteList();
    delete cache;
    return 0;
}

6. 可选：优化链表查找效率 #

当前链表是尾插，每次查找需要从头遍历。因为斐波那契递归是从n往1计算，缓存里的项会按1、2、3...n的顺序依次插入，本身是有序的，对于n=50来说，遍历成本可以忽略，不需要额外优化。

内容的提问来源于stack exchange，提问作者Martin Kudela