3

I'm trying to write a program that returns the Pell numbers sequence based on a given number.

For example (pellNumb 6) should return a list (0 1 2 5 12 29 70)

This is my code so far. I am able of calculating the numbers, but I am not able of skipping the double recursion. 

(defun base (n)
  (if (= n 0)
      0
      (if (= n 1) 
          1))) 

(defun pellNumb (n)
  (if (or (= n 0) (= n 1))
      (base n)
      (let ((x (pellNumb (- n 2))))
        (setq y (+ (* 2 (pellNumb (- n 1))) x))
        (print y))))

The output for (pellNumb 4) is 2 2 5 12, and this is because i'm recursing to (pellNumb 2) twice.

Is there a way to skip that, and store these values in a list ?

Thanks!

Sylwester
  • 47,942
  • 4
  • 47
  • 79
  • Your `base` function is pointless, since it maps `0` to `0`, `1` to `1` and returns `nil` for everything else. Your caller only calls it in the `0` and `1` case, in which the expression `(base n)` reduces to `n`. – Kaz Nov 08 '18 at 23:51
  • The useless `base` function could also be cutely written as `(case n (0 0) (1 1))`, or `(case n ((0 1) n))`. – Kaz Nov 08 '18 at 23:51

1 Answers1

7

Get the nth number

Yes, there is a way - use multiple values:

(defun pell-numbers (n)
  "Return the n-th Pell number, n-1 number is returned as the 2nd value.
See https://oeis.org/A000129, https://en.wikipedia.org/wiki/Pell_number"
  (check-type n (integer 0))
  (cond ((= n 0) (values 0 0))
        ((= n 1) (values 1 0))
        (t (multiple-value-bind (prev prev-1) (pell-numbers (1- n))
             (values (+ (* 2 prev) prev-1)
                     prev)))))
(pell-numbers 10)
==> 2378 ; 985

This is a standard trick for recursive sequences which depend on several previous values, such as the Fibonacci.

Performance

Note that your double recursion means that (pell-numbers n) has exponential(!) performance (computation requires O(2^n) time), while my single recursion is linear (i.e., O(n)). Moreover, Fibonacci numbers have a convenient property which allows a logarithmic recursive implementation, i.e., taking O(log(n)) time.

Get all the numbers up to n in a list

If you need all numbers up to the nth, you need a simple loop:

(defun pell-numbers-loop (n)
  (loop repeat n
    for cur = 1 then (+ (* 2 cur) prev)
    and prev = 0 then cur
    collect cur))
(pell-numbers-loop 10)
==> (1 2 5 12 29 70 169 408 985 2378)

If you insist on recursion:

(defun pell-numbers-recursive (n)
  (labels ((pnr (n)
             (cond ((= n 0) (list 0))
                   ((= n 1) (list 1 0))
                   (t (let ((prev (pnr (1- n))))
                        (cons (+ (* 2 (first prev)) (second prev))
                              prev))))))
    (nreverse (pnr n))))
(pell-numbers-recursive 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)

Note that the recursion is non-tail, so the loop version is probably more efficient.

One can, of course, produce a tail recursive version:

(defun pell-numbers-tail (n)
  (labels ((pnt (i prev)
             (if (= i 0)
                 prev ; done
                 (pnt (1- i)
                      (cond ((null prev) (list 0)) ; n=0
                            ((null (cdr prev)) (cons 1 prev)) ; n=1
                            (t
                             (cons (+ (* 2 (or (first prev) 1))
                                      (or (second prev) 0))
                                   prev)))))))
    (nreverse (pnt (1+ n) ()))))
(pell-numbers-tail 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)
sds
  • 58,617
  • 29
  • 161
  • 278
  • Hey thanks for the answer. Is there a way to put the values in a list ? –  Nov 07 '18 at 18:50
  • Sure: `(multiple-value-list (pell-numbers n))`, but why would you want it instead of `multiple-value-bind`? – sds Nov 07 '18 at 18:55
  • no they mean all of them, not just the last two. --- also, are you sure it's quadratic and not exponential? – Will Ness Nov 07 '18 at 18:57
  • The assignment asked that the results of the recursion would be stored in a list such that `(pellNum 6)` should return (0 1 2 5 12 29 70) –  Nov 07 '18 at 18:57
  • @WillNess: you are right - I just could not believe is was *that* bad ;-) – sds Nov 07 '18 at 19:08