2

I'm trying to write a recursive function that will reverse a string, I'm pretty sure my basis for the recursion is solid, but I can't get it to work...

Basis: if the length is <= 1 stop. Else, swap the first and last elements and advance one element forward and reduce the length by 1.

I'm having trouble with reducing the length by 1...

I thought about using strcat and add the first element in front with each recursion but it's only good for constants...

Note2: I can't change the signature of the function and I can't use any other libraries.

Do not edit the libraries and commands I use here. These are the ones I know and use.

#include <string.h>
#include <iostream>

using namespace std;
void recuverse(char s[]);
int main()
{
    char s[] = "abcde";
    recuverse(s);
    cout << s << endl;
}

void recuverse(char s[]){
    int len = strlen(s);
    int i;

    if (len <= 1)return;
    else{
        for (i = len-1; i>0; i--){

            swap(s[0], s[i]);

            recuverse(s + 1);
        }
    }
}
1
  • 5
    Moderator Note: I've purged the comments. Most of them didn't seem helpful. Focus on the issue that the OP asked about, and quit worrying about whether or not you can write void main(). Dec 26, 2014 at 19:34

12 Answers 12

2

The for loop inside the implementation is not necessary: you are performing too many swaps as the result of having that loop. In fact, the whole point of this exercise has been to eliminate the loop.

Fix your implementation by adding an extra function that measures the length of the string once, and then calls a two-argument recuverse_impl, like this:

void recuverse_impl(char *s, size_t len) {
    // Base case
    if (len < 2) return;
    // Swap elements the two ends
    swap(s[0], s[len-1]);
    // then call recuverse_impl again
    recuverse_impl(s+1, len-2);
}

void recuverse(char s[]){
    recuverse_impl(s, strlen(s));
}

If a requirement for whatever reason has been to disallow passing the length explicitly, you could change the implementation as follows:

void recuverse(char *s) {
    // Compute the length
    size_t len = strlen(s);
    // Do the base case
    if (len < 2) return;
    // Squirrel away the last element, and replace it with '\0'
    char t = s[len-1];
    s[len-1] = '\0';
    // Make a recursive call
    recuverse(s+1);
    // Now complete the swap
    s[len-1] = s[0];
    s[0] = t;
}

Demo.

5
  • OP says on another answer that recuverse itself must be recursive, and not delegate to another recursive function. I don't know why, but it must.
    – Puppy
    Dec 26, 2014 at 19:27
  • @Puppy: dumb requirements don't allow us to give dumb solutions, like argument passing via globals (would do the trick, but hey). Dec 26, 2014 at 19:29
  • Thanks for saving me time to say this. @puppy
    – shinzou
    Dec 26, 2014 at 19:30
  • Is size_t a must here?
    – shinzou
    Dec 26, 2014 at 19:37
  • 2
    @kuhaku No, but that's the type returned by strlen. You can use an unsigned int or even an int instead, and things will continue to work. Dec 26, 2014 at 19:38
2

My C solution uses no extra libraries (stdio instead of iostream), and the same function signature.

#include <stdio.h>
#include <string.h>

void recuverse(char s[]){
    char saved;
    int len = strlen(s);
    if (len > 1) {
        saved = s[len-1];   // keep last char    
        s[len-1] = 0;       // shorten string
        recuverse(s+1);     // with shorter string
        s[len-1] = s[0];    // replace last char with first
        s[0] = saved;       // replace first char with last
    }                       // job done
}

int main()
{
    char str0 [] = "";      // test with various
    char str1 [] = "a";
    char str2 [] = "ab";
    char str3 [] = "abc";
    char str4 [] = "abcd";

    recuverse (str0);
    printf ("'%s'\n", str0);
    recuverse (str1);
    printf ("'%s'\n", str1);
    recuverse (str2);
    printf ("'%s'\n", str2);
    recuverse (str3);
    printf ("'%s'\n", str3);
    recuverse (str4);
    printf ("'%s'\n", str4);
}

Program output

''
'a'
'ba'
'cba'
'dcba'
2

Try this:

void recuverse(char s[])
{
    int len = strlen(s);
    if (len <= 1)
        return;
    char c = s[len-1];
    s[len-1] = 0;
    recuverse(s+1);
    s[len-1] = s[0];
    s[0] = c;
}
2
  • I never downvote... you can see that in my profile as well. i.imgur.com/eCK986l.png
    – shinzou
    Dec 26, 2014 at 20:32
  • @kuhaku: OK, thanks. Anyways, I slightly improved the answer by saving only one character (instead of two) at every step of the recursion. This should reduce stack usage by a magnitude of 2, thus reducing the risk of getting a stack-overflow during runtime. Dec 26, 2014 at 20:49
2

It seems that I have understood what you need that is what approach you are trying to implement.

You could write the function like

void recuverse( char s[] )
{
    recuverse( s , std::strlen( s ) );
}

void recuverse( char s[], size_t n )
{
    if ( !( n < 2 ) )
    {
        std::swap( s[0], s[n-1] );
        recuverse( s + 1, n - 2 );
    }
}

But it is a wrong solution because it is not function void recuverse( char s[] ); that is a recursive function. It is function void recuverse( char s[], size_t n ); that is recursive. But according to your assignment it is function void recuverse( char s[] ); that shall be recursive.

So the only correct solution is the following.

#include <iostream>
#include <utility>

char * recuverse( char s[] )
{
    if ( *s  )
    {
        char *p = s;

        do
        {
            std::swap( *p, *( p + 1) );
        } while ( *p++ );

        recuverse( s );

        std::swap( *p, *( p - 1 ) );
    }

    return s;
}


int main() 
{
    char s[] = "abcde";

    std::cout << s << std::endl;
    std::cout << recuverse( s ) << std::endl;

    return 0;
}

The output is

abcde
edcba

This recursive function uses neither standard function except std::swap that you can also substitute for your code.:)

I prefer that the function would have return type char * the similar way as standard C string functions. If you want that the function would have return type void then it will look like

void recuverse( char s[] )
{
    if ( *s  )
    {
        char *p = s;

        do
        {
            std::swap( *p, *( p + 1) );
        } while ( *p++ );

        recuverse( s );

        std::swap( *p, *( p - 1 ) );
    }
}

For to understand how this reverse function works without standard function strlen let consider its operations step by step using simplified example "abc".

So we have string with terminating zero

abc\0

which I will write as abc0

The while loop

while ( *p++ ) ...

swaps characters until it will swap the terminating zero.

In the first recursive call the loop is doing the following

abc0
bac0
bca0
bc0a

Now the function calls itself but now the string looks like

bc0

So in the loop there will be

bc0
cb0
c0b

In the next recursive call the argument will be

c0

In the loop the two characters are swapped

0c

So at last the function is called with an empty string. So it simply returns the control to the caller and the caller swaps last characters of the string

Take into account that the whole string now looks like

0cba

We need to move the terminating zero tp its valid position at the end of the string. This is done with the swap after the loop.

0c => c0
--------
c0b => cb0
-----------
cb0a => cba0

That is all.:)

15
  • 1
    Can you add some explanation on while ( *p++ ); please?
    – shinzou
    Dec 26, 2014 at 20:42
  • plus 1, nice inefficient solution, like random sort :) Dec 26, 2014 at 20:42
  • This is very interesting but I also don't get how the while loop doesn't execute with *p == 0 because of the post increment.
    – Galik
    Dec 26, 2014 at 20:45
  • @Lashane It is a splendid solution. I never see such a solution before that a string could be reversed without strlen.:) Dec 26, 2014 at 20:45
  • @VladfromMoscow do .. while (*p) is kinda strlen Dec 26, 2014 at 20:46
2

As near as I can tell, this is the only way to accomplish what you ask for with such unreasonable restrictions.

This would be a stupid, stupid way to write this function, but I believe it does what was asked for within the specified guidelines.

// Reverses a string in place.
// Note: string cannot be a constant, without write permission
void reverse(char s[])
{
    // Get string length
    int len = strlen(s);

    if (len > 2)
    {
        // Save last character
        char lastChar = s[len - 1];

        // Temporarily shorten string by replacing last character
        // with a null-terminator character
        s[len - 1] = '\0';

        // Recursively swap remaining characters
        reverse(s + 1);

        // Swap first and last character
        s[len  - 1] = s[0];
        s[0] = lastChar;
    }
}

I consider the approach above to be a bad one because recursion is not the most efficient way to approach this problem. And even if recursion is used, it would be far more efficient to write a separate function for the recursive portion of this code, which could include additional arguments to track state and prevent some of the repeated logic here. Also, it makes no sense to avoid any other libraries, particularly if that includes the libraries that will be part of any C++ application anyway.

Without these restrictions, here's how I might approach writing a reverse function.

void reverse(char* s)
{
    char *pEnd = s + (strlen(s) - 1);
    while (s < pEnd)
    {
        char c = *s;
        *s++ = *pEnd;
        *pEnd-- = c;
    }
}
1
  • Why is it that stupid to write it this way? (you could use strlen there btw)
    – shinzou
    Dec 26, 2014 at 19:59
1

here is proper version of recursive reverse:

void reverse(char *s, char *e) {
    if (s < e) {
        char t = *s;
        *s = *e;
        *e = t;
        reverse(s+1, e-1); // here is length is decreased by 2
    }
}

void recuverse(char s[]) {
    int len = strlen(s);

    reverse(s, s+len-1);
}
17
  • 2
    Is this tested? Doesn't your use of swap swap the pointers instead of the characters? Dec 26, 2014 at 19:01
  • @kuhaku function signature is not changed Dec 26, 2014 at 19:05
  • This isn't a recursive function, it's an outline for a recursive function.
    – shinzou
    Dec 26, 2014 at 19:05
  • 1
    @kuhaku: People are trying to help you. Maybe you should stop acting like a dick. This is a recursive function. And Puppy, what is your problem with the revised code? Without testing it, it appears correct to me. Dec 26, 2014 at 19:14
  • 2
    @Cheersandhth.-Alf just to stop useless discussion whether it c or c++, I've decided just "implement" swap which will work in both languages Dec 26, 2014 at 19:27
1

This is not changing the signature, but it is using std::swap to swap s[begin] and s[end] until it reaches the middle. To accomplish recursion and also keep the signature, you can (doens't mean you should) declare begin, mid and length as global variables:

int beg = 0;
int len = 0;
int mid = 0;

void recuverse(char s[]) {
    if (beg == 0) { // this block runs one time.
        len = strlen(s)-1;
        mid = len / 2;
    }
    if (beg == mid)
        return;
    swap(s[beg], s[len]);
    ++beg, --len;
    recuverse(s);
}

Output: edcba

5
  • @kuhaku: You can just call this function from a function with your preferred signature. Note that that signature does not support a direct recursive solution. Dec 26, 2014 at 19:21
  • What is the purpose of the string argument, and why on Venus do you call it n? Dec 26, 2014 at 19:22
  • @0xB00B5 Thanks but it isn't recursive.
    – shinzou
    Dec 26, 2014 at 19:48
  • @kuhaku, edited again for recursion but you should know there are much better ways to accomplish this, if you were allowed to have another signature.
    – Andreas DM
    Dec 26, 2014 at 20:03
  • @0xB00B5 yes I'm aware of that, it'll be more easy too. Thanks again, I'll have a look.
    – shinzou
    Dec 26, 2014 at 20:06
1

if you are allowed to use static variable, try this

void recuverse(char s[]){
    static int e;
    int z=strlen(s)-e++;           // z is the number of characters to be evaluated
    if(z>1){    
        char t=*(s+z-1);
        *(s+z-1)=*s;
        *s=t;
        recuverse(s+1);
    }
}
0

If you remark that mirror(cs) = cat(mirror(s),c) (c being a char and s a string) then :

void rev(char *s) {
  if (*s==0) return;
  rev(s+1);
  sprintf(s,"%s%c",s+1,*s);
}
2
  • OP says: no additional library functions.
    – Puppy
    Dec 26, 2014 at 19:10
  • Ok, change the sprinttf call to the right while loop... char c = *s; while (*(s+1)) { *s = *(s+1); s++; } *s = c; Dec 26, 2014 at 19:50
0

Below C++ implementation do recursively reverse a string

Here Base Case is finding the NULL character in string

    #include<bits/stdc++.h>
using namespace std;


    void reverse(string s,long i){


        if(s[i] == '\0')
        return;


        reverse(s,i+1);

        cout<<s[i];
        return;
    }

    int main(){


        string s;

        cin>>s;


        reverse(s,0);
        return 0;
    }
1
  • 1
    "can't change the signature of the function" Dec 26, 2014 at 19:19
0

Try this:

#include <string>
#include <iostream>

std::string reverse(std::string inString)
{
    if (inString.empty()) return "";  // the base case
    
    // push last_char from inString onto the stack
    char last_char = inString.back();  
   
    // remove last char from inString (last pop will create base case)
    inString.pop_back(); 

    // recursive call with shortened inString
    std::string outString = reverse(inString); 
    
    /* pop lastChar(s) off of the stack, inserting in zero index of 
       OutString as they come off the stack. */
    return outString.insert(0, 1, last_char);  
}


int main()
{
    std::string s( "Hello bobaloogie" );

    std::cout << s << '\n';
    std::cout << reverse(s) << '\n';

    return 0;
}

It produces the following output:

Hello stack Overflow
wolfrevO kcats olleH
-1

You can try this :

#include <string.h>
#include <iostream>

using namespace std;

void recuverse(char *s, int right);

int main()
{
    char s[] = "abcde";
    recuverse(s , 0);
    cout << s << endl;
}

void recuverse(char *s, int right){ // Here right is the position of the right position(from right to left) of character with which you will swap
    int len = strlen(s);
    int i;

    if (len <=right)return;

    swap(s[0], s[len-1-right]);

    recuverse(s + 1, right+1);
}
2
  • "can't change the signature of the function" Dec 26, 2014 at 19:17
  • 1
    Please don't try this; this code is illegal, since main is never allowed to return void.
    – Griwes
    Dec 26, 2014 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.