# Recursive reverse

• (2 Pages)
• 1
• 2

## 17 Replies - 2509 Views - Last Post: 13 March 2009 - 07:56 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=92191&amp;s=5ec59fd3b1f1b7ed8df76c61371edd5f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 MikeAbyss

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

# Recursive reverse

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

• D.I.C Lover

Reputation: 2034
• Posts: 5,436
• 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.

### #3 r.stiltskin

• D.I.C Lover

Reputation: 2034
• Posts: 5,436
• 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?

### #4 r.stiltskin

• D.I.C Lover

Reputation: 2034
• Posts: 5,436
• 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

### #5 r.stiltskin

• D.I.C Lover

Reputation: 2034
• Posts: 5,436
• 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.

### #6 baavgai

• Dreaming Coder

Reputation: 7361
• Posts: 15,285
• 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.

### #7 r.stiltskin

• D.I.C Lover

Reputation: 2034
• Posts: 5,436
• Joined: 27-December 05

## Re: Recursive reverse

Posted 12 March 2009 - 05:35 AM

baavgai, 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.

### #8 baavgai

• Dreaming Coder

Reputation: 7361
• Posts: 15,285
• Joined: 16-October 07

## Re: Recursive reverse

Posted 12 March 2009 - 06:39 AM

r.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.

### #9 r.stiltskin

• D.I.C Lover

Reputation: 2034
• Posts: 5,436
• 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.

• D.I.C Regular

Reputation: 58
• 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!

### #11 r.stiltskin

• D.I.C Lover

Reputation: 2034
• Posts: 5,436
• Joined: 27-December 05

## Re: Recursive reverse

Posted 12 March 2009 - 09:58 AM

Linkowiezi, 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.

### #12 MikeAbyss

Reputation: 11
• 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

### #13 r.stiltskin

• D.I.C Lover

Reputation: 2034
• Posts: 5,436
• 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.

### #14 baavgai

• Dreaming Coder

Reputation: 7361
• Posts: 15,285
• Joined: 16-October 07

## Re: Recursive reverse

Posted 12 March 2009 - 06:04 PM

MikeAbyss, 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.

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

### #15 r.stiltskin

• D.I.C Lover

Reputation: 2034
• Posts: 5,436
• Joined: 27-December 05

## Re: Recursive reverse

Posted 12 March 2009 - 07:22 PM

baavgai, 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.