I am trying to do assignmet that we had on test from Algorithms and I am struggling to implement fibbunaci for higher n (range of numbers).

I have to make program that tak n from range n > 5O and the output is last n-th member of Fibunacci sequence. I have to use dynamic structure and recursion. Also I can use only standart libraries (so no matrix, containers vectors etc.)

By dynamic structure i figuered they mean some sort of chained list so I managed to make this code

#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;
}

This only works for n < 34. But I need to make this work for n > 50. I am trying to figure out some optimalization and I figured that the only way is to save values and call them in the calculation but I am struggling to see if it still would be recursion.

Could somebody please guide me in right direction what could I change to make it run for count n > 50. Also I´m not sure if I am ment to use Class because I am tried to implement it on code that we were doing on seminar.

P.S. Please dont judge my code I am starting an
I´m not good at coding so please don´t judge. Just trying to prepare on exam and trying to learn how to complete these assignments.

I don’t expect someone to complete this assignment just trying to figure out what to improve so I can learn and pass my exam