Fibonacci function (was: Newbie questions)
Mon Mar 27 06:19:10 CEST 2006
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
> 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>
More information about the erlang-questions