;; - recursion -
;;
;; The fibonacci sequence is a classic example
;; for application of a recursive algorithm.
;; Each number in the fibonacci sequence is the sum
;; of the two previous numbers
;;
;; (fibr n) => fibonacci(n)
;;
(define (fibr n)
(if (< n 2) 1
(+ (fibr (- n 1))
(fibr (- n 2)))))
;; - iteration -
;;
;; Much faster than with recursion, the sequence can be
;; built using an iterative algorithm. In this example
;; the entire sequence up to certain number n is built
;; and returned.
;;
;; (fib n) returns a list of all
;; fibonacci numbers up to n
;;
;; (fib n) => (1 1 2 3 5 8 13 21 ...)
;;
(define (fib n)
(let (f '(0 1))
(dotimes (i n)
(push (+ (f -1) (f -2)) f -1))
(1 f)))
;; - generator -
;;
;; A generator keeps state in between different repeated
;; calls and remembers the results in a growing list fibo:mem.
;;
;; (fibo) gets called reepeatedly
;;
;; (fibo) => 1
;; (fibo) => 2
;; (fibo) => 3, 5 8 13 21 ...
;;
;; fibo:mem => (0 1 1 2 3 5 8 13 21 ...)
;;
(define (fibo:fibo)
(if (not fibo:mem) (set 'fibo:mem '(0 1)))
(push (+ (fibo:mem -1) (fibo:mem -2)) fibo:mem -1))
;; eof
syntax highlighting with newLISP and syntax.cgi