Mickey Mathieson a écrit :
> I am new to the group and have noticed a lot of questions of
> recursion.
> A problem that is suitable for recursion should produce a smaller
> function that if the problem was solved without recursion. This has
> not been the case from the postings that i have looked at.
>
> I have provided an example of recursion done correctly to reverse a
> string. Notice how short and compact the code is. This is the object
> of recursion - less code at the expense of more memory being used.
>
> Mickey M.
> senior software engineer
> http://www.constructionpartner.com
>
>
> // Reverse String
> char *RevStr(int count, char *str)
> {
> char Value;
>
> if (count)
> {
> Value = str[count-1];
> RevStr(count-1, str);
> }
>
> if (count)
>
this test has no use, since count did not change since the last test
> str[strlen(str) - count] = Value;
>
> return(str);
> }
>
To made even shorter (and poor efficiency... strlen is called far too
often, hope you newer reverse very long string)
char *RevStr(int c, char *str) {
if (c) {
char Value = str[c-1]; // some C compiler could complain about
inside declaration of Value
str[ strlen( RevStr( c-1, str ) ) - c] = Value; // strlen is
stable
}
return(str);
}
A simple iterative one could be (IMHO far more efficient else there is a
bug)
char* reverse( char* str ) {
char* begin = str, *end = str;
while( *end ) ++end; // go to the end
while( end > begin ) { // swap begin and end until they join
char c = *--end;
*end = *begin;
*begin++ = c;
}
return str;
}
and a C++ one could be (a one line)
std::reverse( str, str + strlen( str ) );
> int main(int argc, char* argv[])
> {
>
> char Test[20] = "ABCDEFGHIJK";
> char Out[20];
>
> strcpy(Out,RevStr(strlen(Test), Test));
>
>
> return 0;
> }
>
>
A function like Ackermann could have been a better example of
recursivity efficiency.
When I tought about it, I wonder if this is not a fake to hide some
homework...
Regards,
David
