Recursive String reversal returning reversed string

19 Years Ago ~s.o.s~ 0 200 Views

Hello to everyone out there. Recently many people on different forums have been asking how to make a recursive function which reverses the string passed to it. But unlike the normal recrusive funtion which only prints out the reversed string, this implementation returns a pointer to reversed string.

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

/**
* The actual recursive algo which works behind the scenes
*
* @author ~s.o.s~
* @param src_string The pointer to constant character string which is to be used for reversing
* @param dest_string     The pointer to the string which will hold the reversed string
* @return a pointer to the reversed string
*/
char* _string_reverse( const char* src_string, char* dest_string )
{
     if( *src_string != '\0' )
    {
        *dest_string-- = *src_string++ ;
        _string_reverse( src_string, dest_string ) ;
    }

    return dest_string ;
}
/**
 * Acts as a simple interface which the main function or any function can call, hides the recursive nature of algo used.
 *The creation of the string to be returned occurs in this function which is then used by the recursive alg
 *
 * @author ~s.o.s~
 * @param my_string The const string to be reversed
 * @return Returns the reversed string
 */
char* string_reverse( const char* my_string )
{
    int length = strlen( my_string ) ;
    char* reversed = (char*) malloc( length + 1) ;
    reversed[ length ] = '\0' ;
    char* tmp = &( reversed[ 0 ] ) ;    /// preserve the original pos for returning
    reversed = &(reversed[ length - 1 ]) ;
    reversed = _string_reverse( my_string, reversed ) ;
    return tmp ;
}
/** The driver function which calls the core functionality
* @author ~s.o.s~
*/
int main( void )
{
    const char* my_string  = "Hello All !!" ;
    char* reversed = string_reverse( my_string );
    printf( "\n\nOriginal String: %s and Reversed String: {%s}", my_string, reversed ) ;

    return 0 ;
}

Dani AI

Generated 6 Months Ago

Good idea, — allocating the result in a wrapper and keeping the input const is the right direction. A few practical fixes and clarifications will make the implementation safer and easier to read.

The unsafe bits to watch for

The recursive helper in the original returns a pointer that has been decremented past the start of the buffer; that return value is not usable on its own. Save and return the allocated buffer from the wrapper instead.
Relying on pointer arithmetic inside the helper to position the write location makes the code hard to reason about. Let the helper return the next write position while unwinding the recursion, and set the NUL terminator in the wrapper.
Check malloc for failure, use size_t for lengths, and remember the caller must free() the returned buffer.
For very long strings recursion may hit the stack; ’s iterative alternative avoids that. was also right to flag the distinction between read-only input and a writable result buffer.

A clearer recursive pattern

allocate len+1 in the wrapper,
call a helper that recurses to the end and returns the next write pointer,
write characters during the return phase, then terminate and return the original buffer.

Example (safe pattern):

#include <stdlib.h>
#include <string.h>

static char *rev_write(const char *src, char *dst)
{
    if (*src == '\0') return dst;
    char *p = rev_write(src + 1, dst);
    *p++ = *src;
    return p;
}

char *string_reverse(const char *s)
{
    size_t len = strlen(s);
    char *buf = malloc(len + 1);
    if (!buf) return NULL;
    char *end = rev_write(s, buf);
    *end = '\0';
    return buf; /* caller must free(buf) */
}

Checklist before merging into real code

handle NULL input, check malloc return, avoid casting malloc in C, document ownership (caller frees), and prefer the iterative version for very large inputs.

bumsfeld 413 Nearly a Posting Virtuoso

19 Years Ago

I can't believe it needs to be that complex!

~s.o.s~ 2,560 Failure as a human

19 Years Ago

It is complex since rather than just printing out the reversed string, it "actually" returns a reversed string and that too using recursion.

Have a go at it urself and you will understand its not that simple to handle.

roverphoenix 0 Newbie Poster

19 Years Ago

actually it looks complex bcoz you have initialized the array in read only memory it would be easier if you had dynamically allocated the array making it r+w

Ancient Dragon 5,243 Achieved Level 70

19 Years Ago

Here is a non-recursive version of the same.

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

char* _string_reverse( const char* src_string, char* dest_string )
{
	char *src_ptr = (char*)src_string + strlen(src_string)-1;
	char *dest_ptr = dest_string;
	
	while( src_ptr > src_string)
	{
		*dest_ptr++ = *src_ptr--;
	}
	*dest_ptr = 0;
	return dest_string;

}

int main()
{
	char inbuf[] = "Hello World";
	char outbuf[255] = {0};

	char *result = _string_reverse(inbuf,outbuf);
	printf("%s\n",result);

	return 0;
}

~s.o.s~ 2,560 Failure as a human

19 Years Ago

actually it looks complex bcoz you have initialized the array in read only memory it would be easier if you had dynamically allocated the array making it r+w

I dont know if I quite get you but are you saying that I should have created the input string dynamically and then modified the same ?

But thats not what I wanted to do, I wanted to keep the input string intact. Also creating two functions -- a interface and one actual functionality helps me get rid of using a static type qualifier.

roverphoenix 0 Newbie Poster

19 Years Ago

by dynamically I meant doing a malloc and reading from stdin, and I mentioned read only memory since I thought you had used static char * earlier making the string read only, (thts the case with const char * as well), anyhow since thts not what you intended to do thts fine.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.