Write a pseudocode using recursion to reverse such a sentence word by word. E.g., if the input sentence is A quick brown fox jumps over the lazy dog, the output needs to be dog lazy the over jumps fox brown quick A. Put your pseudocode, including all your sources, in a file called recursiveReverseWords.pdf. You cannot make the linked list doubly linked.

2. Implement your pseudocode. You are provided a file called recursiveReverseWords.cpp with a main function and the function declaration. Do not change the function declaration. The input parameter and return types must be as specified. You will need to include your implementation in this file. The main function includes some test cases.

In a separate file called LinkedList.h, you will find the template declaration for a linked list with the basic functionalities implemented. For bonus points, implement a function that checks if the element you insert into the linked list is a word (i.e., does not contain special characters or white spaces).

//recursiveReverseWords.cpp

#include

#include "LinkedList.h"

using namespace std;

string reverseWords(LinkedList list);

int main() {

LinkedList list; //A quick brown fox jumps over the lazy dog

list.insertBack("A");

list.insertBack("quick");

list.insertBack("brown");

list.insertBack("fox");

list.insertBack("jumps");

list.insertBack("over");

list.insertBack("the");

list.insertBack("lazy");

list.insertBack("dog");

cout << "Original sentence: ";

list.print();

string s = reverseWords(list);

cout << "Reversed sentence: ";

cout << s << endl; // Expects: dog lazy the over jumps fox brown quick A

list.clear();

list.insertBack("Thursday"); //Thursday

cout << "Original sentence: ";

list.print();

s = reverseWords(list);

cout << "Reversed sentence: ";

cout << s << endl; // Expects: Thursday

list.clear();

list.insertBack("Algorithms"); //Algorithms and Data Structure Design

list.insertBack("and");

list.insertBack("Data");

list.insertBack("Structure");

list.insertBack("Design");

cout << "Original sentence: ";

list.print();

s = reverseWords(list);

cout << "Reversed sentence: ";

cout << s << endl; // Expects: Design Structure Data and Algorithms

return 0;

}