Reversing a string in C using Recursion

Question

I have written a program to reverse a string using recursion. But the output I get is an empty string always.

I want to know what is wrong with my logic?

#include<stdio.h>

void reverse(char a[], int start, int end)
{
    char t;
    if(start>=end)
        return;
    else
    {
        t = a[start]; a[start] = a[end]; a[end] = t;
        reverse(a,++start,--end);   
    }
}

int main(void)
{
    char a[] = "hello";
    int n = sizeof(a)/sizeof(a[0]); 
    printf("Given string is : %s ",a);
    reverse(a,0,n-1);
    printf("Reversed string is : %s ",a);
    return 0;
}

The output:

enter image description here

Printing the individual characters I get,

enter image description here

Why would you ever want to use recursion for this? The program was too fast? Consumed too little memory? Source code too readable? — Lundin
– Lundin, Commented Nov 17, 2014 at 14:13
Lundin: This could be homework or simply him trying to learn a bit about recursion with a simple functionn. — hugomg
– hugomg, Commented Nov 17, 2014 at 14:14
@hugomg Good, then he can forward my questions to his teacher. Or sum them up as "Why are you teaching bad programming practice?" — Lundin
– Lundin, Commented Nov 17, 2014 at 14:15
One small suggestion: If I were you I would have used start+1 and end-1 instead of ++ and --. The variable mutations are unnecessary and only serve to confuse things. — hugomg
– hugomg, Commented Nov 17, 2014 at 14:15
@Lundin trees use recursion completely and so too dynamic programming. So to get the basics right I am learning recursion first then I will move to divide and conquer algorithmic strategy then dynamic programming and finally trees. — xxx
– xxx, Commented Nov 17, 2014 at 15:10

Dan · Accepted Answer · 2014-11-17 14:13:07Z

9

Your string is actually 6 bytes long - 'h', 'e', 'l', 'l', 'o', '\0'. The last character is a null byte, which is a string terminator. It signals to functions like printf or strlen where the string ends. When you call reverse, it reverses the entire string, so now the terminator is the very first byte, and printf interprets that as an empty string.

There are two ways to fix this. Either make the index that you pass to reverse one smaller (call reverse(a, 0, n-2)), or use strlen instead of sizeof (int n = strlen(a)).

answered Nov 17, 2014 at 14:13

Dan

10.8k2 gold badges41 silver badges58 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

xxx Over a year ago

That was the mistake. I didn't consider the null character. Thanks

Sourav Ghosh · Accepted Answer · 2014-11-17 14:16:35Z

1

Always remember, the array index for nth element will be n-1.

Your array has 6 elements, so the index will run from 0 to 5, the last [6th] elemst being the NUL terminator.

As per your logic, the NUL terminator becomes the first element in the reversed array, hence no output as string.

Following the logic, your first call to reverse() should be reverse(a,0,n-2); to avoid the NUL being put as the first element in reversed array.

answered Nov 17, 2014 at 14:16

Sourav Ghosh

135k17 gold badges192 silver badges271 bronze badges

1 Comment

xxx Over a year ago

That was the mistake. I didn't consider the null character. Thanks

Collectives™ on Stack Overflow

Reversing a string in C using Recursion

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related