Recursive string reverse

[JBIRD304]

Hey guys. I'm trying to write a string reversal recursively but I have to use only a string and and int as the function parameters. The protoype is strRev(string s , int length); Wouldn't I need more than that to do this? This is what I have so far. I know I'm way off base here.

  #include <iostream>
#include <string>;
using namespace std;

string strRev(string , int );

string strRev(string s , int length)
{
	if (length == 0)
		return 0;
	else 
		return strRev(length -1);
}

	

[Smac89]

If the length is zero, return the empty string otherwise return the last character in the original string plus the recursive call

http://www.cplusplus.com/reference/string/string/operator+/

[Duthomhas]

It also helps to remember a string is a list of characters.

To help with the recursion, a little notation.

Consider that the string "smile" is the same as the string "s" + "mile".

Let's change " and " for ( and ).
Now (smile) == (s (mile)).
And (mile) == (m (ile). Etc.

Last, let's not forget the empty string () at the end of every non-empty string, making
(smile) == (s (m (i (l (e ())))))

If that got you lost, that's OK. Read it again a few times until you get it. (Really! I'm not just messing with you here.)

This idea of the head of a list and the rest of a list is the basic principle in all recursion. (It's particularly useful to look at it that way when you are dealing with lists of things -- like a string. :O)


Now we know that if we are given the string "smile" (which is the list {'s', 'm', 'i', 'l', 'e', '\0'}, or in our new notation, (s (m (i (l (e ())))))), that we can take the first item off and have the remainder of the string.

    first-item = 's'
    remaining = "mile" (or (m (i (l (e ()))))).

To reverse it, I need to add things in the opposite order.

I got 's' + "mile", I want to give reverse("mile") + 's'.

That's a hint.

A standard string knows its own length, so your function does not need a 'length' argument.

string strRev( string s )
{
  if (s.length() == 0)
    return /* string is empty (), what do I return? */
  else
    return /* what is the reverse of first in s + rest of s? */
}

Hope this helps.