string reverse. cannot find the bug in my code.

Hello All,

I have written a program to reverse a string using recursion. Have tried to dry run it , debug it but still can't find the issue. Below is my code:

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void reverse(char *,char *);
int main()
{


char input[] = "Keshav";
char * reversed = (char *)malloc(strlen(input) +1 );
reverse(input,reversed);
puts(reversed);

return 0;

}


void reverse(char * input,char *reversed)
{
	puts("entering reverse");
        
	
	static int i = 0;	
	while(*++input != '\0')
		reverse(input,reversed);	
reversed[i] = *--input;
	reversed[i+1] = '\0';
	i++;
}

Outentering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
entering reverse
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

I am not able to understand why is it entering reverse more than string-length("Keshav") times. Also when I try to debug the local variable input is always pointing to "v" but it should not as every call to reverse must have it's own pointer.

Request anybody to help.

This my first post and pardon me if I have done any mistake.

C Language Operator Precedence Chart

Give that a read.


Quzah.

Hmm.. Have give that a read still seems fine.. while debuging, the local variable or the formal argument 'input' always keeps pointing to the last character v. But according to my understanding it should be taking the value of the local variable of that call. While iterating through the string, I have checked using gdb.. input is correctly moving one step each time.. so when the stack is popped it should go the reverse way..
Any Idea where I am wrong ..?


Thanks


Nitin

Usually if your recursive function needs loops or static variables, it's a hint that it's not designed correctly. As a matter of fact, those two things make your program quite hard to follow.

It helps to say something more than just "entered reverse". Try this for your reverse function. The algorithm is the same, I just added a little extra info:

Code:

void reverse(char * input,char *reversed)
{
    static int depth = 1;
    static int i = 0;


    printf("Entering reverse, depth = %d, input = %s\n", depth, input);
    while(*++input != '\0') {
        depth++;
        reverse(input,reversed);
    }
    reversed[i] = *--input;
    reversed[i+1] = '\0';
    i++;
    depth--;
}

Notice that input shrinks then grows, then shrinks then grows. You call it first with "Keshav", at a recursive depth of 1 (i.e. one instance of the reverse() function on the call stack). That loops through the string, calling reverse with "eshav", "shav", "hav", "av", and "v", each with a recursive depth of 2. Each of those then loops through every letter in the string it was passed, so at depth 2, "eshav" calls reverse with "shav", "hav", "av" and "v", each with depth 3. This goes on to a depth of 6.

You need to define a proper base case, which would be when input points to the null terminator of the original string. You should also start reverse at the end of the allocated memory:

Code:

int main(void)
{
    char input[] = "Keshav";
    char *reversed = malloc(strlen(input) + 1);

    reverse(input, reversed + strlen(input) - 1)
    // null terminate reversed, print output and free(reversed)

    return 0;
}

void reversed(char *input, char *reverse)
{
    if (*input == '\0')  // base case, do nothing
        return;

    // no loops or static variables, just assign through the pointers and increment/decrement, then recurse
}

Oh, it should have been obvious to me.

Code:

void reverse(char * input,char *reversed)
{
    static int i = 0;  
    while(*++input != '\0')
        reverse(input,reversed);   
    reversed[i] = *--input;
    reversed[i+1] = '\0';
    i++;
}

You are recursively calling a function inside a loop. Each time it returns, it's still in a loop, so it just calls the function again.


Quzah.

This was a disaster programming technique....hmm..I was using while rather than an if to check my base condition.. was stuck on this thing for so long....

Thanks guys..


Great example that when the mind bends one way.. it's tough to bend it the other way .. :P

BTW I was trying to follow such a complex path.. so as to try reversing a string without using strlen(). I wan't to further improve on this.. so that my function reverse takes only one argument and reverses that very input.. or so to say an "in place reversal". I don't want to do the below:

Code:

 void reverse(char *s)
{
    int i = 0;
    int j = strlen(s) - 1; //don't wana replace this with a for loop to count the length.
    while (i < j)
    {
        char c = s[i];
        s[i++] = s[j];
        s[j--] = c;
    }
}

Any other suggestions ?


Nitin

Nope, that's about as basic as it gets. You could save yourself the i and j variables by using two pointers instead, but it's not any simpler, just a tiny bit different.

This doesn't work as-is, but you could try doing something similar:

Code:

int tmp = s;
char *q = s + strlen(s);

while (q != tmp)
   *s++ = *q--;

s = q;

@getnitin15: You didn't null terminate your string.

@memcpy: Nor did you, but at least you have a disclaimer

Originally Posted by getnitin15

BTW I was trying to follow such a complex path.. so as to try reversing a string without using strlen(). I wan't to further improve on this.. so that my function reverse takes only one argument and reverses that very input.. or so to say an "in place reversal". I don't want to do the below:

Imagine I gave you a set of children's letter blocks, in a row, on the table. Now I ask you to reverse the blocks, in place. (using no other place to temporarily store the blocks aside from one small space on the table, that holds only one block at any time).

How would you do that, without knowing which block was the last one in the row of blocks?

Try it with bits of paper marked with letters, and see if you can do it, WITHOUT knowing where the end of the set of letters is.

If you can't do it, neither can your program.
If you can do it, please share how! XD

He he.. was just wondering...just gave an interview in amazon... and the guy was trying to get me to optimize everything... need to get out of that shell.. xD

Originally Posted by getnitin15

and the guy was trying to get me to optimize everything...

You could do it without strlen() or taking a count, but I don't think it will matter one way or another.

Code:

void reverse (char *str) {
	int i = 0, mid = 0, j = 0;
	char ch;
	while (str[++i] != '\0');
	i--;
	mid = i/2;
	while (i > mid) {
		ch = str[j];
		str[j++] = str[i];
		str[i--] = ch;
	}
}

I think this disproves Adak -- the analogy would be closing your eyes, putting your hand on the first block, then moving your hand along until you feel the last block, swapping them, then moving your hands in by one and swapping again until your hands touch. Technically, you never have to know exactly how long the row of blocks is.

Originally Posted by MK27

You could do it without strlen() or taking a count, but I don't think it will matter one way or another.

Sorry, MK - whether you note it or not, you have in fact, used strlen() type logic, in your first while() statement, to find the final value of i.

In the table top analogy, it might be equivalent to using proprioception, instead of eyesight. Either way, you have to know where both ends of the string are, to do an efficient in-place, reversal of the string.

If anyone can disprove that, I'm all ears.

Code:

#include<stdio.h>
size_t rev( char s[], size_t x )
{
    if( s && s[x] )
    {
        size_t y = rev( s, x+1 );
        if( x < y / 2 )
        {
            char t = s[x];
            s[x] = s[y-1-x];
            s[y-1-x] = t;
        }
        x = y;
    }
    return x;
}

int main( void )
{
    char foo[] = "Hello World!";
    
    printf( "%s\n", foo );
    rev( foo, 0 );
    printf( "%s\n", foo );
    
    return 0;
}

Recursive in-place reversal without knowing the length ahead of time.


Quzah.

Originally Posted by Adak

Sorry, MK - whether you note it or not, you have in fact, used strlen() type logic, in your first while() statement, to find the final value of i.

Sure, but I never directly compare to the length. OTOH, I do use the value of i/2 and compare to that, which is more or less the same thing. So I accede you are right, I fudged.

If anyone can disprove that, I'm all ears.

If quzah hadn't beaten me to the punch I would have thought of that too, really :P.