Please solve this in c++

Overview. This week's task is to implement four recursive functions, two of which relate to linked lists. Functionality is not enough; all your functions must be recursive. The first function is to compute the nth value of a recursively defined sequence, the second is a recursive version of a function implemented for your midterm, the third recursively constructs a linked list from an array, and the fourth recursively deletes the dynamic memory associated with a linked list. Implement all functions in the only file you should upload. Don't modify the corresponding four function signatures provided for you, and as always, do not add any libraries. A test file ma in. cpp is provided for you along with the node. h interface and corresponding inline implementations. You may use the main program however you like; you won't upload your test code. To test, compile as follows: g++main.cppnode.cppstd=c++11 Function 1. Write a function to recursively compute the nth item in the following sequence: a0=1,a1= 1,a2=2,a3=3,a4=5,a5=7,a6=10,a7=13,, where an=an2+n1 for n2. Your function must be recursive. Function 2. Write a function to recursively reverse the order of the elements in an array of integers. The function will be called on an array, specifying the first and last index of the array to reverse. Your array reversal should be in-place, meaning you should not allocate any additional arrays on the stack or on the heap. Your function must be recursive. Function 3. Write a function to recursively construct a linked list with contents as specified by an array. The head pointer should be point to a node with data a [0] that links to a node with data a [1], and so on. Your function must be recursive. Function 4. Write a function to recursively delete the memory for all nodes in a dynamically allocated linked list. The head pointer should be null when the function is complete, and no memory should be orphaned. Your function must be recursive. I/ overloaded for debugging ostream\& operator (ostream\& out, const node * head) \{ if (head==nullptr) return out; // base case: empty list out head > data() " "; // non-recursively output the data of the head return (out head link() ); // recursively output everything else 3 I/ stubs for HW8 functions Int f1( int n){ return 1;} void f2 (int * a, int first, int last) \{\} void f3 (node' "\& head, node "\& tail, int * a, int n ) \{\} void f4 (node "\& head, node "\& tail), }