Recursively reversing words in a string

Question

My friend got an assignment and I can't help him. Basically, using recursion he needs to print the words of a sentence in the reverse order. For example: Input - This is a sentence Output - sentence a is This

Here is an example I wrote him for a normal print, and I could do the whole sentence reversal with no problem, but I can't get neither an idea of a starting point for reversing only the words recursively without a linear approach and using the string library or linked lists or any other way:

#include <iostream>

using namespace std;

void revSentence(char sentence[], int i)
{
  if (sentence[i] == 0)
    return;
  cout<<sentence[i];
  i++;
  revSentence (sentence, i);
}

int main()
{
  char sentence[100];

  cin.getline (sentence, 100);
  int i = 0;

  revSentence(sentence, i);

  return 0;
}

Thing is it probably is something very simple because he is doing a fast course with only the basics, so they didn't use anything but the iostream library, so it must be something simple or at least not too complicated. So I'm asking for at least an idea of approach, or a solution. I've got a feeling I'm missing something very simple here but just can't see it.

Thanks in advance

Answer 1

• It's not as easy as you might think.

• You need to change the location where the printing command is called and place it below revSentence() recursive call, this is called post-order traversal, while the one you are doing is called pre-order traversal.

• You also need a stack to push the reversed words.

---

#include <iostream>
#include <string>
#include <stack>

void revSentence(std::string const &str, std::stack<char> &stk, int i) { 
  if(i == str.size()) return;
  revSentence (str, stk, i + 1);
  if((!stk.empty() && stk.top() != ' '  && str[i] == ' ') || i == 0) {
    if(!i) std::cout << str[i];
    while(!stk.empty()) { 
        std::cout << stk.top();
        stk.pop();
    }
    if(i) std::cout << str[i];
  }
  stk.push(str[i]);
  if(!i) std::cout << std::endl;
}

int main() {
  std::string sentence;
  std::stack<char> stk;
  std::getline (std::cin, sentence);
  int i = 0;
  revSentence(sentence, stk, i);

  return 0;
}