Re: C style , one argument, recursive, string reverse
On 29 May 2006 12:15:43 -0700, "zahy[dot]bnaya[At]gmail[dot]com"
<zahy.bnaya@gmail.com> wrote:
First, a C newsgroup would be better suited for this discussion,
despite the fact the source in your original posting was tainted by
C++ iostreams. We're so far into it at this point we may as well
finish it here.
All previous advices were good and appreciated..
Sorry about my stubborness I am really intrested to know why my code
does not work
That's an admirable trait in a programmer.
I remarked it better.
I know it is probably not the best way to do it but can you see a
problem in there?
I see three levels of problems. The most basic you're already aware
of: the recursive approach is not the best design because of time and
space inefficiencies. The other two are problems of logic (i.e. is
the implementation correct?) and problems of style/micro-optimization
(like the basic level but applied to statements rather than design).
When I'm having problems with an algorithm, I follow Feynman's lead
and try it out with a specific test case. I'll use a call of
'C_recReverse("12345")' as an example.
not for the sake of solving the problem , just for education...
Thanks.
It is an interesting approach, and even though there turns out to be a
better one, considering alternate approaches keeps the mind flexible.
/*
Algorithm pseudo:
reverse(str)
if(str="")
return ""
else
return append(last_char(str),
reverse(all_but_last_char(str))
*/
char * C_recReverse(char * str)
{
// Sub is storing the substring
// res is the returned string
// tmp is for storing the previos result so it can be deleted
char* sub, *res, *tmp;
if (strlen(str) == 0)
return "";
else
{
/* the sub and res are allocated per recursion stack*/
sub = (char*)malloc(sizeof(char)*strlen(str)-1);
Logic error. 'strlen("12345")' == 5, so 'sub' is allocated 4
characters, one of which must be '\0' (e.g. 'sub' can hold "123").
Need to hold 6 ('strlen(sub)+1).
res = (char*)malloc(sizeof(char)*strlen(str));
Logic error. 'res' can hold 5 characters (e.g. "5432"), but need to
hold 6.
/* prepering the substring, stored on the heap*/
strcpy(sub,str);
Logic error. Copies 6 characters from 'str' into 'sub'. That's 2
characters more than 'sub' can hold. Undefined behavior; possible
segfault.
sub[strlen(str)-1] = '\0';
Logic error. In our example, that's 'sub[4] = 0'. The maximum legal
index for 'sub' is 3.
/* the return value is preperaed , filled with last char*/
strcpy(res,"");
strncpy(res,&str[strlen(str)-1],1);
Logic error: 'res' may be improperly terminated. Imagine 'res'
points to previously used memory ("raths outgrabe."). After
'strcpy(res,"")', 'res' points to "\0aths outgrabe.". After the 2nd
strcpy, 'res' points to "5aths outgrabe."; there's now no terminator
within the bounds of 'res'. The next call to 'strcat' will place
characters after the '.'. Another possible segfault.
Micro-optimization: Each line assigns a single character within 'res'.
More efficient alternative:
res[0] = str[strlen(str)-1];
res[1] = '\0';
/* calling the reverse function of the "sub" stored
on local variable tmp*/
tmp = C_recReverse(sub);
/* adding the result of substring reverse to the result string (res)
*/
strcat(res,tmp);
/*"closing" the string (???) */
res[strlen(str)] = '\0';
Micro-optimization. 'strcat' will terminate the destination string;
no need for this line.
/* Freeing the substring, I dont really need it anymore*/
free(sub);
/* Freeing the "previous" recursion closure,
Can I do it? I think this is the
problem */
free(tmp);
This step is necessary. 'C_recReverse' allocates a char array
(pointed to by 'res') that it doesn't free. After a recursive call to
'C_recReverse', 'tmp' points to such an array and the calling
'C_recReverse' is now responsible for the memory.
return res;
}
}
Thanks.