Recursive function to reverse the words of string

[redfury]

Hello, I am supposed to make a recursive function which will reverse the words in the string..
I have made one program but that program reverses all the characters... How can I do the same thing for the words? I know it has something to do with the "space" in between words but I just can't seem to make a logic... Will it require more than 1 array? or what?
Here's my program for the reverse of characters though. It is quite a simple program, which will make a dynamic array depending upon size of entered string and then input the characters from last to first one.

#include <iostream>
#include <string>
using namespace std; 
char *fun(char *, char *, int);
int size(char *); 
int main()
{
	string name; 
	cout << "Enter String: ";
	getline(cin, name);
	char *p; 
	int a = size(&name[0]);
	char *rev = new char[a];
	p = fun(&name[0], rev, a-1);
	cout << p; 
	cout << endl;
	system("pause");
	return 0;

}
int size(char *name)
{
	int z;
	for (z = 0; *name != '\0'; z++)
		name++; 
	return z; 
}
char *fun(char *name, char *rev, int a)
{
	static int z = 0; 
	rev[z] = name[a];
	z++; 
	if (a == 0)
	{
		rev[z] = '\0';
		return rev; 
	}
	a--; 
	return fun(name, rev, a); 
}

This is what you would get if you enter, "Hello World"

Enter String: Hello World
dlroW olleH
Press any key to continue . . .

Whereas, the desired output should be, "World Hello"
I don't want the whole code, just the logic that I should be using here to get the work done.
Thank you!

[keskiverto]

Note: You never deallocate the array you made with new. Learn to manage the memory, or use library types that do it for you. For example, std::string rather than array of char (as C-string).

This ain't quite:

#include <iostream>
#include <string>
#include <sstream>

void snafu( std::istream& in ) {
  std::string word;
  if ( in >> word ) { // #1
    snafu( in ); // #2
  }
  std::cout << ' ' << word; // #3
}

int main()
{
  std::string name = "Sparrow Jack Captain";
  std::istringstream foo( name );
  snafu( foo );
}

The recursion does three operations:
#1 Makes a copy of the first word (of the remaining string). Also checks for end.
#2 Processes the rest of the string
#3 Appends the copy made in #1 into the result string


std::string has append. One could result += word;

std::string has size. name.size().
Is the std::string always null-terminated?

[Duthomhas]

Some thoughts to help you through:

   0123456789012
  "Hello world!"
   ↑    ↑      ↑
   ↑    ↑      end of string
   ↑    ↑
   ↑    end of first word
   ↑
   beginning of first word

Reverse string starting at beginning and ending at (ending - 1)

   0123456789012
  "olleH world!"
         ↑     ↑
         ↑     end of string
         ↑     ↑
         ↑     end of next word
         ↑
         beginning of next word

Reverse string starting at beginning and ending at (ending - 1)

   0123456789012
  "olleH !dlrow"
               ↑
               end of string
               ↑
               beginning of next word... er, no more words

Done.
You now have a string with all the word in the original order, but the letters reverse.

   0123456789012
  "olleH !dlrow"
   ↑           ↑
   ↑           end of string
   ↑
   begin string

Reverse string starting at begin and ending at (end - 1)

   0123456789012
  "!dlrow olleH"

All done!

Notice how the common things to do are:
  • reverse a (sub)string
  • find the beginning of the next word (find not space characters)
  • find the end of the current word (find the next space character)

Those common things should inform functions to help you out.

After that you can apply your algorithm with a single loop.
Time Complexity: O(3n)
Space Complexity: O(1)

Hope this helps.