Recursive Reverse Void Function

[wsad597]

Hey everybody,

So I'm working on a homework problem.
We are implementing a bunch of different functions to manipulate and test c-strings. The catch is we are doing every function two ways: iteratively and recursively. I have done all of the other functions both ways but I'm stuck on recursive reverse function.

Okay so I've been trying to work this out for several hours now and I seem to be going in circles.
The problems I'm dealing with are:
1.) it has to be a void function
2.) the only arguments it can take are the source c-string(forward) and destination c-string(to be in reverse).


It really would be a very simple if I didn't have to worry about those things.
So this is what I kind of left off on. It doesn't reverse the string but copies it over which was something.

void str_reverse_r ( const char str1[], char str2[] )
{
	/*
	*	this only works when we assume that str2 is empty at start
	*/
	if( (*str1)!='\0' ){
		str_reverse_r(str1+1, str2+1);
	}
	(*str2)=(*str1);
	return;
}

If someone could give me a few pointers or talk me through some pseudo code I would really appreciate it.

And here is a program to run the function:

#include <iostream>
using namespace std;

void str_reverse_r ( const char str1[], char str2[] )
{
	/*
	*	this only works when we assume that str2 is empty at start
	*/
	if( (*str1)!='\0' ){
		str_reverse_r(str1+1, str2+1);
	}
	(*str2)=(*str1);
	return;
}

int main(){
	char test[100]="abcdef";
	char fill[100]="";

	cout<< "String ::"<< test<< "::\n\n";
	fill[0] = '\0';
    str_reverse_r(test, fill);
    cout << "recursive reverse::"<< fill << "::\n";

char p;
cin>> p;
return 0;
}

Thank you in advance.

[TheCreator]

void str_reverse_r (const char *str[], char str2[])
{
          int max=strlen (*str);
          int min=0;

          while (max!=0)
         {
          *str[max]=str2[min];
          max--;
          min++;
         }

}

[shacktar]

Hint: Fill the destination string with all '\0's to begin with*. Start the pointer in the first string at the first character (position 0, or simply test) and start the pointer in the second string at the last character
(fill + strlen(test) - 1).

*You can do that like this:

char fill[100] = {0};

@TheCreator That's not recursive.

If someone could give me a few pointers

http://xkcd.com/138/

Sorry I had to.

[wsad597]

Thank you so much for the speedy reply.
I see where you are going but it doesn't really help in this situation because it's

-not recursive
-accepting a value pointed by a reference instead of a reference
-it's modifying a constant


here is my iterative version without comments:

void str_reverse_i(const char str1[], char str2[])
{
	int len=(str_length_i(str1))-1;

	for(int i=0; i<len+1; i++){
		str2[i]=str1[len-i];
	}
	
	str2[len+1]='\0';

	return;
}

[shacktar]

I ninja'd you. See my response above. Hope it helps.

[wsad597]

HAH!
I actually always sneak that in when I'm asking for programming help!
No one has ever picked up on it.


This is very good advice.
So in order to make them all null characters wouldn't I have to do that outside of the function though?

[shacktar]

So in order to make them all null characters wouldn't I have to do that outside of the function though?

Yes.

char test[100] = "abcdef";
char fill[100] = {0};

cout<< "String ::"<< test<< "::\n\n";

str_reverse_r(test, fill + strlen(test) - 1);

cout << "recursive reverse::"<< fill << "::\n";

[wsad597]

Ahh. yes. That's actually a clever idea.
The thing is that I can only augment the guts of the function.


I fiddled around with maybe using a static variable to keep track of the function calls or something like that but it seemed weaselly and I was sure there was a better way. (plus I've never used static and I didn't want to go too crazy)

As far as starting from the back of the string to be loaded; do you have any ideas how I could do that while nested several stacks down in a function?

The code I posted earlier - if you take out the +1 after "str2+1" on line 7, it replaces the 0th element of the array of str2 with the right order of letters, but the problem is it 'replaces' them. If I could somehow increment the position in str2 on the way down I might have a chance but I never got anywhere.


My teacher must think there is some simple way to solve this but I just can't figure it out.

[wsad597]

Then again I cant use static because I have to call my function multiple time for different sets of data in the same run. Never mind that.

[helios]

Alright. It can be done without calling other functions and using two static integers. Hint: you'll need a way to know when you're at the top of the recursion, at the bottom, and how deep you are.

[kev82]

I don't see any requirement that prevents you calling strlen (or your own implementation) in your recursive function. If so what's the problem?

[wsad597]

Thank you so much guys. It has really helped to bounce ideas off of you and get different points of view.

I think I actually figured it out. What did it was when you brought up that I could use predefined functions. I was thinking too narrowly.
Instead of strlen I used strncat.

void str_reverse_r ( const char str1[], char str2[] )
{
	/*
	*	this only works when we assume that str2 is empty at start
	*/
	if( (*str1)!='\0' ){
		str_reverse_r(str1+1, str2);
		strncat(str2, str1, 1);
	}
	return;
}

[wsad597]

Recursion always surprises me in its simplicity of looks(the fact that I spent hours working at it, not withstanding)

[shacktar]

Here's what I was going for (only predefined function use is strlen):

#include <iostream>
using namespace std;

void str_reverse_r ( const char str1[], char str2[] )
{
    if( *str1 != '\0' )
    {
        *str2 = *str1;
        str_reverse_r(str1 + 1, str2 - 1);
    }
}

int main()
{
    char test[100] = "abcdef";
    char fill[100] = {0};

    cout<< "String ::"<< test<< "::\n\n";

    str_reverse_r(test, fill + strlen(test) - 1);

    cout << "recursive reverse::"<< fill << "::" << endl << endl;

    cout << "Press ENTER to continue..." << endl;
    cin.get();

    return 0;
}