Documentation typo in CodePatterns

[jef]

Hi,



I realized that the code for the fibonacci functions in the codepatterns

section is wrong: http://www.newlisp.org/CodePatterns.html#toc-5">http://www.newlisp.org/CodePatterns.html#toc-5



The code is:

Code Select Expand

; classic recursion
; slow and resource hungry
(define (fib n)
    (if (< n 2) 1
        (+  (fib (- n 1))
            (fib (- n 2)))))

> (fib 12)
233

Should be:

Code Select Expand

; classic recursion
; slow and resource hungry
(define (fib n)
    (if (< n 2) n
        (+  (fib (- n 1))
            (fib (- n 2)))))

> (fib 12)
144

The iterative version should be fixed also, something like

that should be correct:

Code Select Expand

; iteration
; fast and also returns the whole list
(define (fibo n , f)
  (set 'f '(1 0))
  (case n
    (0 (1 f))
    (1 f)
    (true
      (dotimes (i (- n 1))
        (push (+ (f 0) (f 1)) f)))))

> (fibo 12)
(144 89 55 34 21 13 8 5 3 2 1 1 0)

[Lutz]

It depends what you define as the Fibonacci sequence:



The expression (if (< n 2) 1 sees n as index into the sequence 1,1,2,3,5,8 ...

The expression (if (< n 2) n sees n as index into the sequence 0,1,1,2,3,5,8 ...



The original Fibonacci sequence does not contain a result for (fibo 0) (see the "rabbit" example), and one could argue, that the result for (fibo 0) should not be included but is undefined.



The first form is also faster for the same result:

Code Select Expand


> (time (println (fib1 29)))
832040
459.522
> (time (println (fibn 30)))
832040
738.925
>