Sign in to follow this  

Printing a String Backwards in Recursion?

This topic is 2846 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, im messing around with recursion a little bit and I had a class assignment to do a factorial command using recursion. I got that figured out but then I started to think and wonder if i could print out a string backwards using recursion? I looked on the internet at a couple of examples of people doing it but I can't seem to wrap my ahead around what is actually going on. This is my first year in computer science so I'm not very good at coding yet but I really want to get a hold of recursion before it gets a hold of me :P If anyone has any ideas how I could use recursion to print a string backwards that would be cool to know :) Thanks!

Share this post


Link to post
Share on other sites

#include <iostream>
#include <string>

void printStringBackwards(const std::string& str, unsigned int idx = 0)
{
if( idx < str.length() )
printStringBackwards(str, idx + 1);
else
return;

std::cout << str[idx];
}

int main(int argc, char** argv)
{
printStringBackwards(std::string("Hello, World!"));
return 0;
}


That should work in C++. You could do optimizations etc., but it's a simple example. Basically you want to go from the last character from the first character. So essentially we make use of the call stack by calling the function recursively if we haven't reached the end of the string. If we did reach the end, then we return to the previous call which continues at the output statement.

It's really quite simple. Recursion can be powerful when used correctly. I don't recommend you use it in this instance. An iterative solution would be much preferred.

Share this post


Link to post
Share on other sites
Quote:
Original post by Halifax2
*** Source Snippet Removed ***
That should work in C++. You could do optimizations etc., but it's a simple example. Basically you want to go from the last character from the first character. So essentially we make use of the call stack by calling the function recursively if we haven't reached the end of the string. If we did reach the end, then we return to the previous call which continues at the output statement.

It's really quite simple. Recursion can be powerful when used correctly. I don't recommend you use it in this instance. An iterative solution would be much preferred.


Notice the question :

>> If anyone has any >>>ideas<<< how I could use recursion to print a string backwards that would be cool to know :) Thanks

It would have been better if you gave him some hints or so. Just straight out
giving the answer then explaining it is not more productive(for OP) then making
him/her work hard and then if all fails, then maybe consider giving some code.
I say this, because I believe this is his/her learning stage. But thats just my
opinion, I'm sure people have theirs.

Share this post


Link to post
Share on other sites
The problem is that it's hard to demonstrate the operation of recursion in that simple case, when a simple backwards iteration would suffice.
You need better examples, when for example there is branching in the recursion: the recursing function call itself more than once. For example floodfill algorithms.

The basic benefit of recursion, is to use the call stack as Halifax2 mentioned (I hope that's the right term), so when branching, the information of the next steps (for example coordinates of the next node in floodfill) will be stored and stacked up by the iteration itself, no need to do manual, and not-so-easy memory management.

But that's the only thing I use recursion (floodfill) for, so I guess there are other benefits too (apart of code simpleness).

Share this post


Link to post
Share on other sites
The thing with recursion is, it's not suitable for everything. In you're case, it might be ok for learning, but do some operation recursively with a string would just end up being a waste of time in your code. Thing is, it tend to be slower than using simple loops, but are really usefull sometime, cause a simple recursive function can do a loop with very little code. I mostly use it for iterating through directory, or recently in my maze generator/solving code, but i try to keep using them to a minimum. Also, recursive function can overflow the stack very fast so u might need to use a bigger one than the default 1Mo settings.

Clicky

Share this post


Link to post
Share on other sites
yeah well i already had some code working with it in JAVA but just couldn't seem to get it to print out the right letters backwards. I always end up getting IndexOutOfBounds errors and I'm just struggling haha. I'm not to worried about it because its not an assignment or anything but I would have just liked to know how to do it.

Thanks to everyone.

Share this post


Link to post
Share on other sites
Reversing a string is conceptually different.

string reverse(const string & s) {
if (s.empty()) return ""; // string is empty
char x = s[0]; // first character
string xs = s.substr(1); // remainder of string
return reverse(xs) + x; // combine in reverse order
}


Haskell:

reverse [] = [] // empty string or list
reverse (x:xs) = reverse xs ++ [x] // x = first element of string or list, xs = remainder
// it means exactly same as C++ version

Haskell code is identical to C++ code, or any other version.


One might point out that this is horribly inefficient due to all temporary strings, and they'd be right. This is why recursion is foundation of functional languages, which can, if it is feasible, do the reverse. They can recognize that idioms and implement them iteratively internally.

C/C++, Java, C#, Python, .... all fall into same non-functional category here.

Share this post


Link to post
Share on other sites
To print out the string in reverse, recursively:

Print out the last character. (Unless of course there is no last character; then you just return.)
Print out everything except the last character, recursively.

The obvious way is to make a substring for the recursive call. Naturally, that creates a lot of garbage (temporary) strings. For an N character string, you also have to create an N-1 character string for the first recursive call, an N-2 character string for the next, etc.

To optimize that, we keep passing the original string (so that we aren't copying anything), as well as an index to the "last" character for this recursive call. We pretend that the string only goes up to that length, and print the appropriate character.

That basically re-frames the process:

Print out the current character, unless that's an invalid index (then you're done). You start with the last character, of course, i.e. an index 1 less than the string length.
Decrease the index by 1 and recurse.

Since nothing happens after the recursive call, we can quickly see the control flow: for a string of length N, we output character N-1, then N-2, all the way down to 0. Then we return out of all the recursive calls, but nothing gets done in between the returns.

A compiler can optimize this to get rid of extra setup work for the function calls and all the useless 'return' work at the end, with an optimization called "tail recursion elimination". The net effect is that the machine code is just the same as if you'd written a while loop to do it.

By the way, it is wrong to write "JAVA". The language's name is "Java". It is not an acronym. It doesn't stand for anything.

Share this post


Link to post
Share on other sites

This topic is 2846 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this