Fibonacci function (was: Newbie questions)

[David Hopwood]

Richard A. O'Keefe wrote:
> Nick Linker <xlcr@REDACTED> wrote:
> 	3. Let me define the following function:
> 	    fib(0) -> 0;
> 	    fib(1) -> 1;
> 	    fib(N) -> fib(N-1) + fib(N-2).
> 
> This is a SPECTACULARLY INEFFICIENT way to compute fibonacci numbers
> in *any* programming language.

Yes. See the logarithmic time algorithm at
<http://en.wikipedia.org/wiki/Fibonacci_number#Computation>.

> It's not a tail recursion issue.  It is simply that the computation you
> have specified does about 2**N function calls for argument N (*regardless*
> of language).

To be terribly pedantic, it is *possible* for a language to do automatic
memoization of side-effect-free functions. OTOH, without some annotations to
say which functions are worth memoizing (and to stop the memo table from
growing without bound), that can very often be a pessimization.

-- 
David Hopwood <david.nospam.hopwood@REDACTED>