Recursive function to reverse a string

Question

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);
        }
    }
}

Answer 1

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

Answer 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;
    }
}

Answer 3

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.:)

Answer 4

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);
    }
}

Answer 5

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;
}

Answer 6

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

Answer 7

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'

Answer 8

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.

Answer 9

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);
}

Answer 10

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);
}

Answer 11

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;
    }

Answer 12

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);
}