CODEWITHSUNDEEP
functional-programminglispcommon-lisp
user5831089
user5831089

Reputation:

LISP function to print out fibonacci sequence up to N amount of numbers

I have to write code that computes N Fibonacci numbers (where N is the function parameter). I'm new to LISP and am struggling with the syntax. This is what I have so far... I feel like it is close.

(defun fib (n)
(if (or (= n 1) (= n 2))
(print 1))
(print (+ (fib (- n 1))(fib (- n 2)))))
;;;;It should output like so:
(fib 0)
()
(fib 2)
( 1 1 )
(fib 6)
( 1 1 2 3 5 8 )

Could anyone help me tidy up my function so that it works? Thanks in advance!

Upvotes: 1

Views: 1940

Answers (3)

Mulan
Mulan

Reputation: 135257

Here's another way you can use an auxiliary procedure with a continuation to solve the problem.

This procedure is tail recursive yet does not require reversing the accumulated list of fibonacci numbers.

(define (fib n)
  (define (aux n a b k)
    (if (zero? n)
        (k (list a))
        (aux (sub1 n)
             b
             (+ a b)
             (lambda (rest) (k (cons a rest))))))
  (aux n 0 1 identity))

(fib 0)  ;; => '(0)
(fib 1)  ;; => '(0 1)
(fib 2)  ;; => '(0 1 1)
(fib 10) ;; => '(0 1 1 2 3 5 8 13 21 34 55)

The code here is racket, but you could translate it to Lisp with relative ease.

Upvotes: 0

Sylwester
Sylwester

Reputation: 48745

If you expect (1 1) from evaluating (fib 2) in the REPL then you are not expecting anything to be printed, just that the list (1 1) is to be returned. 

;; using recursion. 
(defun fib (limit)
  (labels ((helper (n a b)
             (if (> n limit)
                 '()
                 (cons a (helper (1+ n) b (+ a b))))))
    (helper 0 0 1)))

;; using tail recursion. Usually tail call optimized when 
;; compiled, but it's not a requirement in the standard.
(defun fib (limit)
  (labels ((helper (n a b acc)
             (if (> n limit)
                 (nreverse acc)
                 (helper (1+ n) b (+ a b) (cons a acc)))))
    (helper 0 0 1 '())))

;; Using loop. Never blows stack.
(defun fib (limit)
  (loop :for a := 0 :then b
        :and b := 1 :then (+ a b)        
        :repeat limit
        :collect a))

I think all these are equally readable so there is no reason not to go for the loop version that is the safest in any implementation.

Note that the first fibonacci number is 0 and that my code reflects that.

Upvotes: 2

Rorschach
Rorschach

Reputation: 32426

The way you are doing it is tree recursive and its running time will blow up exponentially. The link has efficient alternatives. But, if you want to keep the whole sequence you could do something like,

(defun fib (num)
  (let (seq)
    (labels ((helper (n)                                  ; define local helper function
               (when (<= n num)                           ; stop when reached NUM
                 (if (< n 3) (push 1 seq)
                     (push (+ (car seq) (cadr seq)) seq)) ; sum of previous 2
                 (helper (1+ n)))))                       ; recurse
      (helper 1))                                         ; start from first fib number
    (nreverse seq)))                                      ; reverse the result

Upvotes: 0

Related Questions