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 :p

Quote:

---

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

Quote:

---

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

Quote:

---

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.

Quote:

---

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.

Quote:

---

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.

Quote:

---

Originally Posted by MK27

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

---

I think someone was trying to do it for homework here once. I just did it to see if I could. I don't know if I actually posted the result, but I keep it around because I thought it was nifty. :D


Quzah.

quzah..
I guess..

Code:

---

if(s[x])

---

would do as the base condition.. ain't it ?

Nifty it *certainly* is, but efficient - no. I'm sure it would do for most string reversal jobs, though.

Quote:

---

Originally Posted by Adak

Nifty it *certainly* is, but efficient - no.

---

How is it not efficient? What's your metric? It makes a single pass through the string. It's fine if you can actually say why it's not efficient, and I'm not claiming it is. But you are claiming it isn't, so you'll need to do more than what you've done to prove your case.


Quzah.

Quote:

---

Originally Posted by quzah

How is it not efficient? What's your metric?

---

It must use (relatively) excessive stack space, but WRT to speed, I wonder how significant the recursion is?

Code:

---

#include <stdio.h>
#include <sys/timex.h>
#include <stdlib.h>
#include <string.h>

#define LINES 80368

int loadStrings (char *path, char *store[], int len) {
        char *p;
        int i = 0;
        FILE *in = fopen(path, "r");
        if (!in) return -1;
        while (fgets(store[i], len, in)) {
                p = strchr(store[i++], '\n');
                *p = '\0';
        }
        fclose(in);
        return 0;
}

void reportDif (struct ntptimeval *a, struct ntptimeval *b) {
        long mic = b->time.tv_usec - a->time.tv_usec,
                sec = b->time.tv_sec - a->time.tv_sec;

        if (mic < 0) {
                sec--;
                mic *= -1;
                mic++;
        }

        printf("Elapsed: %ld microseconds\n", mic + sec * 1000000);
}

char **allocList (int sz, int len) {
        char **rv = malloc(sz * sizeof(char*));
        int i;
        for (i = 0; i < sz; i++)
                rv[i] = malloc(len);
        return rv;
}

void freeList (char *list[], int sz) {
        int i;
        for (i = 0; i < sz; i++)
                free(list[i]);
}

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

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) {
        int i;
        char **data = allocList(LINES, 32);
        struct ntptimeval start, end;
        loadStrings("dictionary.txt", data, 32);

        ntp_gettime(&start);
        for (i = 0; i < LINES; i++)
                reverse(data[i]);
        ntp_gettime(&end);
        reportDif(&start, &end);
               
        ntp_gettime(&start);
        for (i = 0; i < LINES; i++)
                rev(data[i], 0);
        ntp_gettime(&end);
        reportDif(&start, &end);

        freeList(data, LINES);
        free(data);
               
        return 0;
}

---

Not as big a deal as I would have guessed:

Elapsed: 4801 microseconds
Elapsed: 8216 microseconds

My metric for efficiency would be + 10% to 15%. This is + 71%.

MK did a great job of testing, but his strings were simply single words, I believe. As the strings got longer, the "Nifty" reversing program will begin to flounder much more than the 171% of the better algorithm. Think of the DNA researcher who stated she was working with strings up to 32k in length!! <eek!>

Also, the "Nifty" program is longer, and easier to goof up. Besides it's nifty-ness, it has nothing to recommend it.

Quote:

---

Originally Posted by Adak

Also, the "Nifty" program is longer, and easier to goof up. Besides it's nifty-ness, it has nothing to recommend it.

---

I assume by "longer and easier to goof up" you mean because it has two arguments instead of one. Ok. Here's a non-recursive, in-place string reversal, that still technically uses a single pass through the string. ;)

Code:

---

void revbubble( char s[] )
{
    for( int here = 0; s[ here ] != '\0'; here++ )
    {
        for( int there = here -1; there > -1; there-- )
        {
            char c = s[ there + 1 ];
            s[ there + 1 ] = s[ there ];
            s[ there ] = c;
        }
    }
}

---

Isn't it cute??


Quzah.

Point is, you can't do an efficient in-place string reversal unless you know where the end of the string is. Ideally, the end of the string would be known to the function doing the reversal.

All this other stuff is second rate at the job at best, no matter how cute or nifty it might be.

Quote:

---

Originally Posted by Adak

All this other stuff is second rate at the job at best, no matter how cute or nifty it might be.

---

I wasn't trying to be efficient on any of them. I was going for interesting. Actually the first one was constrained by someone's homework assignment guidelines, and the second one was just interesting. I'll leave efficiency for people who specialize in doing boring things.


Quzah.

Lol. The second one reminds of this toy made of a chain of flat wooden blocks (proportionate to a domino, but ~4" long), held together end to end with three fabric straps. The straps were attached in such a way that you could cause the blocks to flip in a sequence, and what it looked like was one block cartwheeling along the chain.

But it is even slower than the recursive one:

Elapsed: 4798 microseconds
Elapsed: 8220 microseconds
Elapsed: 13687 microseconds

Hmm...found the toy. It's called a "Jacob's ladder":
http://www.lhup.edu/~dsimanek/TTT-rings/rings.htm

Quote:

---

Originally Posted by MK27

But it is even slower than the recursive one:

Elapsed: 4798 microseconds
Elapsed: 8220 microseconds
Elapsed: 13687 microseconds

---

Of course it's slower. It's basically a bubble sort. It just pushes the furthest point back along the line until it's at the front. Over and over. Put in some printf statements if you want to watch it work.


Quzah.