Fibonacci function (was: Newbie questions)

David Hopwood david.nospam.hopwood@REDACTED
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 mailing list