Recursive reverse

  • (2 Pages)
  • +
  • 1
  • 2

17 Replies - 2495 Views - Last Post: 13 March 2009 - 07:56 AM Rate Topic: -----

#1 MikeAbyss   User is offline

  • D.I.C Head
  • member icon

Reputation: 11
  • View blog
  • Posts: 56
  • Joined: 09-July 07

Recursive reverse

Post icon  Posted 11 March 2009 - 06:14 PM

Well my instructor gave me the template for the reverse function...
void reverse( char *s)
{

}



And after an hour this is what I got...

#include <stdio.h>

void swap( char *a, char *b);
void reverse( char *s);

void reverse( char *s)
{
	char *p = s;
	char *q = s;

	if ( *q == '\0' )
	{
		return;
	}
	while( *(q+1) !='\0' )
	{
		q++;
	}
	reverse ( (p+1) );
	swap( p, q );

}

void swap( char *a, char *b)
{
	char temp;
	temp = *a;
	*a = *b;
	*b = temp;

}

int main()
{
	char hello[] = "hello";

	reverse( hello );
	puts( hello );

	getchar();
	return 0;
}



But after that I can't seem to get this recursive function to work, does anyone know how to?

Your help is much appreciated, thanks!

Is This A Good Question/Topic? 0
  • +

Replies To: Recursive reverse

#2 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2032
  • View blog
  • Posts: 5,435
  • Joined: 27-December 05

Re: Recursive reverse

Posted 11 March 2009 - 06:57 PM

Your code has much too much stuff going on. I don't have the energy to analyze it line by line, but here is a recursive reverse function in pseudocode. I will leave it to you to write it in C.

reverse( myArray ) :
  if( myArray.length is 1 )
	return myArray
  return myArray.last + reverse( myArray.allbutlast )


myArray.last means the last actual character, not the null character. myArray.allbutlast means just what it sounds like. "+" means string concatenation.
Was This Post Helpful? 0
  • +
  • -

#3 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2032
  • View blog
  • Posts: 5,435
  • Joined: 27-December 05

Re: Recursive reverse

Posted 11 March 2009 - 09:32 PM

PS: your instructor wants a void function that takes only 1 argument. The recursive algorithm either needs to have a return value (a char* ) or be void but have 2 char* arguments (one for input and 1 for output).

You can accomplish this by making a second "rev_helper" function that is called by the "reverse" function, so you'll end up with something like:
void reverse( char* input ) {
  rev_helper( input, input );
}

void rev_helper( char* input, char* output ) {
 ...
}



Since per your instructions you don't want to preserve the original array, when "reverse" calls "rev_helper", the input pointer is used for both arguments. (But the same is not true whenever "rev_helper" calls itself.)

Does that help?
Was This Post Helpful? 0
  • +
  • -

#4 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2032
  • View blog
  • Posts: 5,435
  • Joined: 27-December 05

Re: Recursive reverse

Posted 11 March 2009 - 10:29 PM

Well, after actually doing it, it seemed to be easier if the helper function returns a char*, i.e.:
char* rev_helper( char* input ) {
...
}

void reverse( char* input ) {
  rev_helper( input );
}



Sorry if I got you off on the wrong track. (Although I'm sure it's possible to do it the other way too.)

This post has been edited by r.stiltskin: 11 March 2009 - 10:30 PM

Was This Post Helpful? 0
  • +
  • -

#5 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2032
  • View blog
  • Posts: 5,435
  • Joined: 27-December 05

Re: Recursive reverse

Posted 11 March 2009 - 11:09 PM

And now I realize that a helper function is not needed at all since we don't have to preserve the input string. You can do it with just the simple void function
void reverse( char* s ) {
..//only 9 lines of (not tricky) code needed here
}



Study the pseudocode I posted. You might find it easier to do it first with a helper function that returns a char*, since that will conform more closely to the pseudocode, and then translate it to a single function.

One more hint: in the reverse function, you will have to define a temporary string to hold the "all but last letter" string.
Was This Post Helpful? 0
  • +
  • -

#6 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7295
  • View blog
  • Posts: 15,185
  • Joined: 16-October 07

Re: Recursive reverse

Posted 12 March 2009 - 04:43 AM

Are you trying to reverse in place or just print it out reversed?

Printing it out reversed with recursion makes a lot of sense. If you want to reverse the actual string, you're going to have to have a second function that will do the work.

For the printing option: Consider what it would take to print a character, increment the pointer, and call yourself to print the next. Stop when that character is zero. It's actually three lines (well, depending on your style and what you consider a line) and depending on where you put those lines, you get forward or reversed.

Good luck.
Was This Post Helpful? 0
  • +
  • -

#7 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2032
  • View blog
  • Posts: 5,435
  • Joined: 27-December 05

Re: Recursive reverse

Posted 12 March 2009 - 05:35 AM

View Postbaavgai, on 12 Mar, 2009 - 06:43 AM, said:

Are you trying to reverse in place or just print it out reversed?


He needs to reverse it in place -- per the function signature he showed in the original post.
Was This Post Helpful? 0
  • +
  • -

#8 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7295
  • View blog
  • Posts: 15,185
  • Joined: 16-October 07

Re: Recursive reverse

Posted 12 March 2009 - 06:39 AM

View Postr.stiltskin, on 12 Mar, 2009 - 06:35 AM, said:

He needs to reverse it in place -- per the function signature he showed in the original post.


I would rather hear this from the OP, since it doesn't state this in their single post. The function signature doesn't lend itself to reverse in place for recursion.

Forgive me if I doubt your psychic ability. :)
Was This Post Helpful? 0
  • +
  • -

#9 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2032
  • View blog
  • Posts: 5,435
  • Joined: 27-December 05

Re: Recursive reverse

Posted 12 March 2009 - 07:03 AM

Sorry, I misspoke. I shouldn't have said he has to do it "in place", but the function signature he was given indicates that he is to replace the input string with the reversed string, not merely print it in reverse.
Was This Post Helpful? 0
  • +
  • -

#10 Linkowiezi   User is offline

  • D.I.C Regular

Reputation: 58
  • View blog
  • Posts: 316
  • Joined: 07-October 08

Re: Recursive reverse

Posted 12 March 2009 - 09:00 AM

Well, despite all the help you might already have gotten I just couldn't keep my fingers from tossing in a solution to your problem that actually uses your 'template function'.
void reverse(char *s){
  int size, i;
  char t;
  
  for(size=0; s[size]!='\0'; size++);
  
  for(i=0; i<=size/2; i++){
    t=s[i];
    s[i]=s[size-i-1];
    s[size-i-1]=t;
  }
}


Hope you found this useful.
And also, happy coding to you! :D
Was This Post Helpful? 0
  • +
  • -

#11 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2032
  • View blog
  • Posts: 5,435
  • Joined: 27-December 05

Re: Recursive reverse

Posted 12 March 2009 - 09:58 AM

View PostLinkowiezi, on 12 Mar, 2009 - 11:00 AM, said:

Well, despite all the help you might already have gotten I just couldn't keep my fingers from tossing in a solution to your problem ...

That is not a solution to the OP's problem because it is not recursive.
Was This Post Helpful? 0
  • +
  • -

#12 MikeAbyss   User is offline

  • D.I.C Head
  • member icon

Reputation: 11
  • View blog
  • Posts: 56
  • Joined: 09-July 07

Re: Recursive reverse

Posted 12 March 2009 - 01:53 PM

I sincerely apologize for all the confusing, but the recursive function *must* change the actually array and store it.

Sorry for the late reply, I've been studying for my midterm on recursions >_<

This is my code now, it works but is it actually recursive?

#include <stdio.h>

/*  Main function will call other functions
	Input: No input
	Output: Outputs 0
*/
void swap( char *a, char *b);
void reverse( char *s);

void reverse( char *s )
{
	char *p = s;
	char *q = s;

	if ( *s == '\0' )
	{
		return;
	}
	while ( *q != '\0' )
	{
		swap( s, q);
		q++;
	}
	reverse( s + 1 );
}

void swap( char *a, char *b)
{
	char temp;
	temp = *a;
	*a = *b;
	*b = temp;

}

int main()
{
	char hello[] = "hello";

	reverse( hello );
	puts( hello );

	getchar();
	return 0;
}



This post has been edited by MikeAbyss: 12 March 2009 - 02:17 PM

Was This Post Helpful? 0
  • +
  • -

#13 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2032
  • View blog
  • Posts: 5,435
  • Joined: 27-December 05

Re: Recursive reverse

Posted 12 March 2009 - 04:39 PM

Well, there's no disputing the fact that your code does reverse the string, but I would argue that it's not really a recursive implementation. I won't be surprised if someone will disagree with me about that, because you clearly use a recursive call in the function. But your function also uses iteration (the while loop), and it is the iterative swapping code that actually does the work of reversing the string. In a purely recursive function, all of the work is done by the recursion and there should be no for or while loops at all.

Look at the pseudocode I posted. It has no loops. The essential elements are:
- a base case (the if statement) whose purpose is to terminate the recursion (otherwise it would keep recursing until it crashes because the available memory is full), and
- a recursive case, in which the recursive function is called with a "smaller" or "simpler" argument, so the each successive recursive call gets closer and closer to the base case.
Aside from that, the only "overhead" operations are related to concatenating the strings.

Here's another example - actual code for a recursive implementation of strlen. I think it's different enough from your assignment so it won't spoil the challenge for you, and may help you get the idea:
// recursive_strlen will crash if input doesn't point to a valid c-string (null-terminated char array)
int recursive_strlen( char* input ) {
  if( *input == '\0' )
	return 0;
  return 1 + recursive_strlen( input+1 );
}


I could also show you a recursive_strcat or recursive_strcpy, but they're so similar to recursive_reverse that I'm reluctant to post them, at least not before you've had the opportunity to try to work it out yourself for a while.
Was This Post Helpful? 1
  • +
  • -

#14 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7295
  • View blog
  • Posts: 15,185
  • Joined: 16-October 07

Re: Recursive reverse

Posted 12 March 2009 - 06:04 PM

View PostMikeAbyss, on 12 Mar, 2009 - 02:53 PM, said:

This is my code now, it works but is it actually recursive?


It's fascinating, but kind of not really recursion. Essentially, it drags the last character to the first position on each pass. Probably not the most efficient solution. :P

You're doing this:
void reverse( char *s ) {
	char *q, temp;
	for(; *s != '\0'; s++) {
		for(q = s; *q != '\0'; q++) {
			temp = *s;
			*s = *q;
			*q = temp;
		}
	}
}




Here's what the reverse print might look like:
void reverse( char* s ) {
	if (*s==0) { return; }
	reverse( s+1 );
	printf("%c", *s);
}



For what you're trying to do, for it to be true recursion, it will require a second function. It would looks some like:

void reverseRecurse(char *head, char *tail);
void reverse( char* s ) {
	reverseRecurse(s, (s + strlen(s)-1));
}



Or, if you want to be really clever about it, this is also possible:
int reverseRecurse(char *s, int index);
void reverse( char* s ) {
	reverseRecurse(s, 0);
}



Good luck.

This post has been edited by baavgai: 12 March 2009 - 06:05 PM

Was This Post Helpful? 0
  • +
  • -

#15 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2032
  • View blog
  • Posts: 5,435
  • Joined: 27-December 05

Re: Recursive reverse

Posted 12 March 2009 - 07:22 PM

View Postbaavgai, on 12 Mar, 2009 - 08:04 PM, said:

For what you're trying to do, for it to be true recursion, it will require a second function.

Actually, no. It can be done with exactly the function signature his teacher provided.

Of course, since C lacks the built-in list handling capabilities of languages like Lisp and Haskell, the recursive_reverse will have to use strlen, strcpy and strcat functions. If he's really ambitious, those can all be implemented recursively as well -- then the entire thing will be purely recursive.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2