Функция LISP для распечатки последовательности фибоначчи до N количества чисел

Question

Мне нужно написать код, который вычисляет числа N Фибоначчи (где N - параметр функции). Я новичок в LISP и борюсь с синтаксисом. Это то, что у меня есть до сих пор ... Я чувствую, что это близко.

(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) 

Может ли кто-нибудь помочь мне убрать мою функцию, чтобы она работала? Заранее спасибо!

Answer 1

То, как вы это делаете, это tree recursive, и его время работы будет взорваться экспоненциально. Ссылка имеет эффективные альтернативы. Но, если вы хотите сохранить всю последовательность вы могли бы сделать что-то подобное,

(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 

Answer 2

Если вы ожидаете (1 1) от оценки (fib 2) в REPL, то вы ничего не ожидая печати, только что список (1 1) является возвращаться.

;; 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)) 

Я думаю, что все они одинаково читаемые, поэтому нет никаких причин, чтобы не идти на версию loop, который является самым безопасным в любой реализации.

Обратите внимание, что первое число fibonacci равно 0 и что мой код отражает это.

Answer 3

Здесь вы можете использовать вспомогательную процедуру с продолжением, чтобы решить проблему.

Эта процедура является хвостовой рекурсивной, но не требует реверсирования накопленного списка номеров фибоначчи.

(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) 

Код здесь racket, но вы можете перевести его в Lisp с относительной легкостью.