12 Replies - 14208 Views - Last Post: 26 September 2010 - 02:56 PM Rate Topic: -----

#1 tswarthog  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 25-September 10

Using Recursion to Reverse a String

Posted 25 September 2010 - 07:37 PM

Hello everyone, I am currently working on a problem where I understand the concept however I cannot seem to wrap my head around the code.

Problem:
I am trying to implement a function called reverse that will take a string it, recursively reverse the string by putting the last character in the string at the beginning of the string to be returned, then concatenate the recursively reversed string minus its last character. After all that return the string as a std::string.

What I understand:
I understand that with recursion you have to have a base case, I believe the base case for this problem is that their are no more letters in the string to reverse (the string is empty) After hitting the base case you would return that string to the line of code that called the function.
Now if the base case is not attained you must then write the last character of the string by calling the function with the string - 1. This will repeat until you have the base case (an empty string).
I can pretty much accomplish this problem outside of a function call but with the parameters I am just lost.

What I don't understand.
I cant seem to get my head around creating the base case and the recursive call to itself with the parameters using actual code. Can anyone explain to me how you create a recursive function like this? I put kinda my idea of what needs to be done in the function.

Code.
#include <iostream>
#include <string>

using namespace std;

string reverse(string& str);

int main() {
   string theString = "";

   cout << "Enter a (backward) string: ";
   getline(cin, theString);

   cout << reverse(theString) << endl;

   return 0;
}

string reverse(string& s) {
 // if (string is empty)
	//  return final string
 // return reverse(the string + string - 1)
 
}



I will be sleeping on this problem so sorry If I do not respond till tomorrow.

This post has been edited by tswarthog: 25 September 2010 - 07:38 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Using Recursion to Reverse a String

#2 no2pencil  Icon User is offline

  • Admiral Fancy Pants
  • member icon

Reputation: 5363
  • View blog
  • Posts: 27,325
  • Joined: 10-May 07

Re: Using Recursion to Reverse a String

Posted 25 September 2010 - 07:43 PM

Quote

string reverse(string& s) {
 // if (string is empty)
	//  return final string
 // return reverse(the string + string - 1)
 
}


I believe that a more effective solution would be a function that is passed a character. The function would recursively call itself until all characters are used, so it would need to check for end of string. Character arrays are better used for this than a string.
Was This Post Helpful? 0
  • +
  • -

#3 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Using Recursion to Reverse a String

Posted 25 September 2010 - 07:53 PM

no2pencil said:

Character arrays are better used for this than a string.
I have to disagree. It's convenient and straightforward with strings.

tswarthog said:

I believe the base case for this problem is that their are no more letters in the string to reverse (the string is empty) After hitting the base case you would return that string to the line of code that called the function.
Really? Let's take an example. Call your recursive function f. f("t") should get you t. Are you telling me that you haven't reached your base case with one single letter?

Quote

Now if the base case is not attained you must then write the last character of the string by calling the function with the string - 1.
Let's do a sanity check. f("the"). So to write the last character of the string, you call f("th"). How do you get 'e' from the string "th"?
Was This Post Helpful? 1
  • +
  • -

#4 no2pencil  Icon User is offline

  • Admiral Fancy Pants
  • member icon

Reputation: 5363
  • View blog
  • Posts: 27,325
  • Joined: 10-May 07

Re: Using Recursion to Reverse a String

Posted 25 September 2010 - 08:07 PM

View PostOler1s, on 25 September 2010 - 08:53 PM, said:

no2pencil said:

Character arrays are better used for this than a string.
I have to disagree. It's convenient and straightforward with strings.

I'm not saying you are wrong, but I've not had much luck using strings in C++. Can you just directly access the element? If so, then I must have really fudged something in my past... :P
Was This Post Helpful? 0
  • +
  • -

#5 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3028
  • View blog
  • Posts: 10,547
  • Joined: 08-August 08

Re: Using Recursion to Reverse a String

Posted 25 September 2010 - 08:24 PM

For starters, you don't want to pass the string by reference unless you don't care about dismantling the original string. As for the function, you want to return the string if it is of length one. If it's not, you want to return the last character plus the reverse of the substring up to but not including the last character!

View Postno2pencil, on 25 September 2010 - 10:07 PM, said:

View PostOler1s, on 25 September 2010 - 08:53 PM, said:

no2pencil said:

Character arrays are better used for this than a string.
I have to disagree. It's convenient and straightforward with strings.

I'm not saying you are wrong, but I've not had much luck using strings in C++. Can you just directly access the element? If so, then I must have really fudged something in my past... :P

Heh, I used to feel the same way, but over time I've flipped to the point where I wonder why we have char at all. Strings are easier to deal with!
Was This Post Helpful? 1
  • +
  • -

#6 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Using Recursion to Reverse a String

Posted 25 September 2010 - 09:05 PM

CTphpnewb said:

For starters, you don't want to pass the string by reference unless you don't care about dismantling the original string.
Of course, if you could find a way to do recursive string reversal without modifying the string, that would be the best. And if you weren't going to modify the string, pass a const reference works best.

no2pencil said:

Can you just directly access the element?
Yes.
Was This Post Helpful? 0
  • +
  • -

#7 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 990
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Using Recursion to Reverse a String

Posted 25 September 2010 - 10:31 PM

View Postno2pencil, on 26 September 2010 - 12:07 PM, said:

Can you just directly access the element?


Yep.
Choice of:
1 - theString.at(pos)
2 - theString[pos]

It's all here:
http://www.cplusplus.../string/string/

After all, under the safety protections and dynamic sizing and all that good stuff they are just character arrays. Just that C++ protects you from a lot of the work and dangers that raw arrays expose you to.
Was This Post Helpful? 1
  • +
  • -

#8 zoopp  Icon User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 15
  • Joined: 25-September 10

Re: Using Recursion to Reverse a String

Posted 26 September 2010 - 03:00 AM

I don't see why you want to use recursion for this. It's easier to do it using reverse iterators.

Something like:

string getReverse(string &str)
{
    return string(str.rbegin(), str.rend());
}

Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5874
  • View blog
  • Posts: 12,752
  • Joined: 16-October 07

Re: Using Recursion to Reverse a String

Posted 26 September 2010 - 04:54 AM

Your sig of string reverse(string& s) offers a little extra confusion. It means you have to create another instance of string. I'm not quite sure how to show this without letting the cat out of the bag...

string reverse(string& s) {
	// if (string is empty) return ""
	// string sr = string - 1
	// return reverse(sr) + [ string of first char ]



That may be more confusing? Ah, hell, let's explain...
reverse("ABC123")
	return reverse("BC123") + "A"
		return reverse("C123") + "B"
		...
			return reverse("") + "3"
				return ""
		...
		return "321C" + "B"
	return "321CB" + "A"



Hope this helps.
Was This Post Helpful? 2
  • +
  • -

#10 tswarthog  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 25-September 10

Re: Using Recursion to Reverse a String

Posted 26 September 2010 - 08:17 AM

View Postbaavgai, on 26 September 2010 - 03:54 AM, said:

Your sig of string reverse(string& s) offers a little extra confusion. It means you have to create another instance of string. I'm not quite sure how to show this without letting the cat out of the bag...

string reverse(string& s) {
	// if (string is empty) return ""
	// string sr = string - 1
	// return reverse(sr) + [ string of first char ]



That may be more confusing? Ah, hell, let's explain...
reverse("ABC123")
	return reverse("BC123") + "A"
		return reverse("C123") + "B"
		...
			return reverse("") + "3"
				return ""
		...
		return "321C" + "B"
	return "321CB" + "A"



Hope this helps.


That has definitely cleared up confusion in regards to implementation, knowing that you need another instance of string to run the recursion pretty much.

(sorry if my lack of C++ is getting annoying, I am just trying to understand the concepts before I go to coding this)
so in the line
//if(string is empty) return"" you are checking the base case, and if that is reached, you want to do nothing.

//string sr = string -1 this is declaring another instance of string, in this case sr, and setting that string equal to the string originally passed in minus 1 (aka the string of the first character)

//return reverse (sr) + [string of first character] you are returning a call to reverse of the new string sr, and adding on the string of the first character described above




Just doing a logic check here.

This post has been edited by tswarthog: 26 September 2010 - 08:17 AM

Was This Post Helpful? 0
  • +
  • -

#11 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3028
  • View blog
  • Posts: 10,547
  • Joined: 08-August 08

Re: Using Recursion to Reverse a String

Posted 26 September 2010 - 10:08 AM

That looks right. My way was the opposite, grabbing the last character and adding to it:

    return "3" + reverse("ABC12")


This post has been edited by CTphpnwb: 26 September 2010 - 10:08 AM

Was This Post Helpful? 0
  • +
  • -

#12 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5874
  • View blog
  • Posts: 12,752
  • Joined: 16-October 07

Re: Using Recursion to Reverse a String

Posted 26 September 2010 - 02:45 PM

You seem to be following. Honestly, the code is shorter than they description. ;)

You have a "string" object. That object offers various methods. I did it with three methods, size, substr, and a string constructor. I also did it in three lines. There are numerous permutations you can use. However, I can assure you that the string class itself has all you need.

If you have not exercised your google fu, do so now. The very first hit I get from this is this. Any solution you go with should start there.

Good luck.

This post has been edited by baavgai: 26 September 2010 - 02:46 PM

Was This Post Helpful? 0
  • +
  • -

#13 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3028
  • View blog
  • Posts: 10,547
  • Joined: 08-August 08

Re: Using Recursion to Reverse a String

Posted 26 September 2010 - 02:56 PM

View Postbaavgai, on 26 September 2010 - 04:45 PM, said:

I did it with three methods, size, substr, and a string constructor. I also did it in three lines.

Same here, but I used length instead of size.

I too worried that the explanation being much longer than the code might be confusing. Just remember that there are really two cases. One is the base case where the string is one character and the other case is where it is longer than one character.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1