>
> I calculate the Fibonnacci numbers without recursion using REBOL. For
> example
...
> How would you calculate it with recursion?
>
> Jerry
>
> 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
If speed is the objective (rather than total correctness ;-) one
could write:
fib2: func [first second n] [
either n > 0 [
fib2 second first + second n - 1
][
first
]
]
placing the "most likely" branch first. This rearrangement saves
just over 25%, according to my quick-and-dirty benchmarking:
>> x: now/time loop 10000 [y: fib 1.0 1.0 100] now/time - x
== 0:01:37
>> x: now/time loop 10000 [y: fib 1.02 1.0 100] now/time - x
== 0:01:12
Of course, both versions compute only the original Fibonacci series
for positive arguments. Both would require modifications (and would
take more time) to deal properly with zero or negative arguments.
Taking the base cases f(0) = 0, f(1) = 1, and the recurrence
relation f(n) = f(n-1) + f(n-2), the Fibonacci function actually has
as domain the entire set of integers...
n: ... -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 ...
f(n): ... 34 -21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 21 34 ...
Therefore, the fastest way to extend either version is to calculate
the (zero-based) result for the absolute value of the argument, then
flip the sign if the argument were even. This would add only a
constant time if implemented via a helper function (which also hides
the initialization of the accumulator arguments), as in:
fibabs: func [first second n] [
either n > 0 [
fibabs second first + second n - 1
][
first
]
]
fib: func [n] [
either even? n [
- fibabs 1.0 1.0 abs n
][
fibabs 1.0 1.0 abs n
]
]
with timing results of
>> x: now/time loop 10000 [y: fib 100] now/time - x
== 0:01:09
>> x: now/time loop 10000 [y: fib -100] now/time - x
== 0:01:09
Of course, this last bit of pedantry is off of the topic of recursion
versus iteration, but I couldn't help myself. ;-)
-jn-
