Thread: string reverse. cannot find the bug in my code.

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    7

    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.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    C Language Operator Precedence Chart

    Give that a read.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    7
    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

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    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
    }

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Mar 2012
    Posts
    7

    Thanks...quzah and anduril462

    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

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    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.

  8. #8
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    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;

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    @getnitin15: You didn't null terminate your string.

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

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by getnitin15 View Post
    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

  11. #11
    Registered User
    Join Date
    Mar 2012
    Posts
    7

    :)

    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

  12. #12
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by getnitin15 View Post
    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.
    Last edited by MK27; 03-03-2012 at 09:32 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by MK27 View Post
    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.

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  15. #15
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Adak View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Exercise reverse array . I can't to find error .
    By ToNy_ in forum C Programming
    Replies: 8
    Last Post: 12-15-2011, 04:02 PM
  2. reverse a string without string.h library
    By antros48 in forum C Programming
    Replies: 6
    Last Post: 09-10-2011, 06:01 PM
  3. Reverse a string (without using any string functions?)
    By geetard in forum C Programming
    Replies: 2
    Last Post: 11-15-2006, 07:42 PM
  4. Problem with my string reverse code
    By learninC in forum C Programming
    Replies: 3
    Last Post: 05-24-2005, 09:22 PM
  5. How to reverse a string C
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 07-18-2002, 12:26 PM

Tags for this Thread