Mickey Mathieson a écrit :
> --- David <[EMAIL PROTECTED]> wrote:
>
>
>> 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
>>
>>
>>
> // Reverse String
> char *RevStr(int count, char *str)
> {
> if (!count) return(str);
> char Value = str[count-1];
> RevStr(count-1, str);
> str[strlen(str) - count] = Value;
> return(str);
> }
>
A variant could have been :
// reverse between [begin,end]
char* reverse_r( char* begin, char* end )
{
if ( end <= begin ) return begin;
char c = *end; *end = *begin; *begin = c; //swap
reverse_r( begin+1, end-1 );
return begin;
}
to remove the strlen bootleneck, and use the symetric property of the
reverse operation
to divide by 2 the depth of recursivity.
reverse_r( Text, Text + strlen( Test ) - 1 );
David
