[Shootout-list] fibonacci and ackermann

[Robert Seeger]

Fair enough. I guess my overall complain is that Ackermann tends to
test the compiler's ability to optimize tail calls and memoization
more than it does the actual cost of recursion.

Compilers/interpreters that performs those optimizations are rewarded,
while those that don't (even if they handle procedure calls very
quickly) are penalized. If the compiler/interp has a recursion limit,
then it may very well just fail the test, no matter how fast it
performs.

I'll have to put some thought, and maybe research, into another way to
solve the problem. Until then, I hold that the Fibonacci test is a
better test of recursion performance.

Rob Seeger

On Apr 3, 2005 2:51 PM, Sebastien Loisel <sloisel@gmail.com> wrote:
> > Any time you use a function with the same input more than once,
> > there's a chance for memoization. Why not just use a function that
> > uses each input only once.
> 
> Good plan, but
> 
> > proc Nsum {n} {
> >     expr { $n + [Nsum [incr n -1]] }
> > }
> 
> a smart compiler might be able to loopify this one, like tail
> recursion. If not, anyone could rewrite it in the tail recursive idiom
> of the language, which would be legitimate but would cause the
> compiler to remove the recursion.
> 
> Ackermann is a *lot* of recursion, but it has the advantage of being
> very nontrivial to optimize away. If you can figure out a recursive
> function that doesn't optimize away, that would be cool too.
> 
> Sebastien Loisel
>