Language Shootout

[Bengt Richter]

On Wed, 11 Jul 2001 14:48:13 GMT, ullrich at math.okstate.edu (David C. Ullrich) wrote:
[...]
>>On my system I get
>>
>>[18:47] C:\pywk\fib>strL.py str  10L**20899
>>str took 13.601617 seconds
>>
>>[18:47] C:\pywk\fib>strL.py strL 10L**20899
>>strL took  1.044989 seconds
>>
>>Recursion rides again ;-)
>
>Recursive or not, the idea that we can write
>a replacement for str that's faster is very
>curious.
>
Well, it's a seldom-used aspect of str to print
monster longs. They surely had more urgent things to do ;-)

>>BTW, how do you put everything inside the strL def
>>to hide names, and how do you recurse inside without
>>a warning message?
I'm leaving this question in ;-)

[...]
>
>Of course you have to do the recursion in a non-stupid
>manner, as here; if you'd made a recurzive routine
>that concatenated Python strings instead of building
>that list I doubt that recursion would win. But it is
>curious how often recursion does seem to win in Python.
>(Doesn't usually beat built-in functions, though.)
>

I hope people realize what you are pointing out,
i.e., that it's not recursion per se that made the gains.
The algorithm is the thing.

Recursion is a powerful way of expressing algorithms,
and the more expressive power you have, the better your
chances of coming up with a good algorithm.
Clean expressive power is Python's main attraction IMO.

A better algorithm can often overcome the advantage of
optimized brute force, and recursion is a natural when
you have foo(x) and can partition x into x1 and x2 such that

    foo(x) == bar( foo(x1), foo(x2) )

and the times for foo-ing the pieces and bar-ing their
results is less than the time for foo-ing the whole.

BTW, if we were recursively searching for the optimumly timed partition
and sub-partitions, UIAM & IIRC it would amount to optimization by
Dynamic programming, I think. You know, the Bellman thing ;-)