[erlang-questions] behavior of funktions

Christian S <>
Mon Jul 23 00:55:18 CEST 2007

A good example is probably this erlang implementation of fibonacci:

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

Pretty much verbatim from http://en.wikipedia.org/wiki/Fibonacci_number

If you call f(10), it will in turn call f(9) and f(8), and f(9) will
call f(8) (again) and f(7), it then continues like this. A whole lot
of redundant computations to get values we already
computed once.

Erlang does nothing to help you here, the number of calls to compute
f(N) will be
(2^N)-1 and most of them redundant. Adding 'memoization' explicitly to
cache the values of
f(N) isnt that easy in Erlang, if you still want to have
pretty/clear/succinct code.

2007/7/23, Johannes <>:
> i never thought of not-side-effect-free functions in that case ;)
> maybe i chosed a bad example.
> My question is, if there is a function, wich is called more than one
> time with the same arguments, how often is it evaluated(not 'called')?
> it's clear, that a its impossible to save all function results the whole
> time a programm is running, but how is it for example in a rekursion ??

More information about the erlang-questions mailing list