fibonnacci

Look back thru the REBOL archives, there was a substantial discussion of it a while back...

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