CODEWITHSUNDEEP
lisp
RoL
RoL

Reputation: 13

Lisp: pell numbers

I have to write a recursive Lisp function that prints the pell number instead of the last number. For example (pellnumbers 6) should return a list (0 1 2 5 12 29 70).

This is my function

(defun pellRecursive (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (+ (* 2 (pellRecursive (- n 1)))
              (pellRecursive (- n 2))))))

but it only prints the final number, can someone please help me? it needs to be recursive.

Upvotes: 0

Views: 70

Answers (1)

user5920214
user5920214

Reputation:

So for a start you will understand why it is almost always better to produce lists like this backwards. Here is an obvious approach to doing that:

(defun pell (n)
  ;; the n'th pell number
  (cond
   ((= n 0) 0)
   ((= n 1) 1)
   ((> n 1) (+ (* 2 (pell (- n 1)))
               (pell (- n 2))))
   (t (error "horror death crust"))))

And now

(defun pell-list (n)
  (if (< n 0)
      '()
    (cons (pell n) (pell-list (1- n)))))

Question: why is this approach terrible (try computing (pell-list 50))?

Here's another function which does the same thing:

(defun pell-numbers (n)
  (cond
   ((= n 0) '(0))
   ((= n 1) '(1 0))
   ((> n 1)
    (let ((pn-1 (pell-numbers (1- n))))
      (cons (+ (* 2 (first pn-1))
               (second pn-1))
            pn-1)))
   (t (error "bad mutant death"))))

Why is this one so much better?

Upvotes: 2

Related Questions