[EMAIL PROTECTED] wrote:
>
> Hi,
>
> I've been following this thread (though it goes over my head a bit) with
> interest, but with this one you guys have lost me! =)
>
> First of all what are Fibonnacci numbers?
>
A famous function used VERY frequently in programming as a kind of
Petri dish for experimenting with recursion. You can find out all
sorts of interesting stuff about them by following the links from:
http://dir.yahoo.com/Science/Mathematics/Numerical_Analysis/Numbers/Fibonacci/
They're often described in terms of problems such as:
Start with one pair of hypothetical newborn rabbits, which can
produce another pair of offspring each month beginning with age
one month (and never die of old age, because they're hypothetical!).
How many pairs of rabbits do you have after N months?
Stepping by months, one get the series:
Month: 1 2 3 4 5 6 7 8 9 ...
Pairs: 1 1 2 3 5 8 13 21 34 ...
Mathematically (and programmatically) they can be defined by the
recurrence relation
F(0) = 0
F(1) = 1
F(n+2) = f(n) + f(n+1) ; or any number of algebraically
; equivalent statements
Running the recurrence BOTH ways from the base values, one gets:
n: ... -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 ...
F(n): ... -21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 21 ...
Computing science types have LOTS of fun inventing various ways to
compute these.
>
> Second, perhaps someone could explain to me what Ladislav's code does?
>
> >
> > fib: func [first second n] [
> > either n = 1 [first] [
> > either n = 2 [second] [
> > fib second first + second n - 1
> > ]
> > ]
> > ]
> >
> > >> fib 1.0 1.0 100
> > == 3.54224848179262E+20
> >
> > Ladislav
> >
It uses tail recursion to accumulate up to the correct answer (for
positive n) starting with the correct answers for n=1 and n=2 in hand.
The initial answers are given in decimal! because the series rapidly
outgrows the range of integer! values (especially on 16- or 32-bit
boxes ;-).
Tracing out the calculation of F(6) using the above function, we get
the following, where the comments are showing what 'first and 'second
"really" are:
fib 1.0 1.0 6 ; F(1) = 1.0 F(2) = 1.0
fib 1.0 2.0 5 ; F(2) = 1.0 F(3) = 2.0
fib 2.0 3.0 4 ; F(3) = 2.0 F(4) = 3.0
fib 3.0 5.0 3 ; F(4) = 3.0 F(5) = 5.0
fib 5.0 8.0 2 ; F(5) = 5.0 F(6) = 8.0
which last line returns 8.0, since n=2. The recurrence relation says
to add a pair of consecutive terms to get the next one, so that's what
this function does, with arguments that always hold two consecutive
terms of the series.
For you trivia buffs, using Ladislav's function above with arguments of
fib 1.0 3.0 n
calculates another recursive series known as the Lucas numbers.
Ah, well, back to coding...
-jn-
