[REBOL] Re: fibonnacci
From: joel::neely::fedex::com at: 1-Oct-2001 13:52
Hi, fellow Fibonacci fan...
mgkiourt wrote:
> Could someone provide a solution to the fibonnacci sequence
> of numbers in REBOL?
>
Given that the Fibonacci sequence is a canonical lab rat for
recursive programming, you can have your choice! (Notes
follow the listing...)
8<----------------------------------------------------------
REBOL []
fibonacci: make object! [
bfib: func [n [integer!]] [
either n > 1 [
(bfib n - 1) + bfib n - 2
][
either n = 1 [
1
][
0
]
]
]
rfib: func [n [integer!] /local .n .rfib] [
.n: do .rfib: func [n [integer!]] [
either n > 1 [
(.rfib n - 1) + .rfib n - 2
][
n
]
] abs n
either all [even? n negative? n] [- .n][.n]
]
tfib: func [n [integer!] /local .n .ifib] [
.n: do .tfib: func [n [integer!] a [integer!] b [integer!]] [
either zero? n [b] [.tfib n - 1 b a + b]
] abs n 1 0
either all [even? n negative? n] [- .n][.n]
]
ifib: func [n [integer!] /local .n a b] [
.n: abs n a: 1 b: 0
while [positive? .n] [
set [.n a b] reduce [.n - 1 b a + b]
]
either all [even? n negative? n] [- b][b]
]
jfib: func [n [integer!] /local .n a b] [
.n: abs n a: 1 b: 0
while [positive? .n] [
.n: .n - 1
b: a + b
a: b - a
]
either all [even? n negative? n] [- b][b]
]
]
8<----------------------------------------------------------
Using the specification
f(0) = 0
f(1) = 1
f(i) = f(i-1) + f(i-1)
there are many ways to code it.
FIBONACCI/BFIB is the brute-force "Fibonacci for dummies" that
is the closest to the pure specification, and also has the
worst time complexity (exponential on argument).
Since
f(i) = f(i-1) + f(i-2)
can be rewritten as
f(i+2) = f(i+1) + f(i)
and thence to
f(i) = f(i+2) - f(i-1)
we can let the argument range over all integers (not just over
the natural numbers 0,1,2,...). All of the rest of the
functions implement for that domain, given the easily provable
facts that
f(-2i) = -f(2i)
f(-2i-1) = f(2i+1)
to handle negative arguments.
FIBONACCI/RFIB is still maximally recursive, although it handles
the full integer domain. It still has exponential time inherited
from BFIB.
FIBONACCI/TFIB is tail-recursive, with linear time complexity.
All of the recursive solutions have linear recursion depth.
FIBONACCI/IFIB and FIBONACCI/JFIB are both iterative, with linear
time complexity. IFIB uses REBOL syntax for parallel updates
to the local words, while JFIB uses a more language-neutral
(but slightly less obvious) technique.
Enjoy!
-jn-
--
This sentence contradicts itself -- no actually it doesn't.
-- Doug Hofstadter
joel<dot>neely<at>fedex<dot>com
