Как не повторяться дважды в ЛИСП - PullRequest
Новая
       10

Как не повторяться дважды в ЛИСП

0 голосов
/ 07 ноября 2018

Я пытаюсь написать программу, которая возвращает последовательность Pell numbers на основе заданного числа.

Например (pellNumb 6) должен вернуть список (0 1 2 5 12 29 70)

Пока это мой код. Я могу рассчитать числа, но не могу пропустить двойную рекурсию. 

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

Выход для (pellNumb 4) равен 2 2 5 12, и это потому, что я возвращаюсь к (pellNumb 2) дважды.

Есть ли способ пропустить это и сохранить эти значения в списке?

Спасибо!

1 Ответ

0 голосов
/ 07 ноября 2018

Получить n th число

Да, есть способ - используйте несколько значений : 

(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

Это стандартный трюк для рекурсивных последовательностей, которые зависят от нескольких предыдущих значений, таких как Фибоначчи .

Производительность

Обратите внимание, что ваша двойная рекурсия означает, что (pell-numbers n) имеет экспоненциальную (!) Производительность (вычисление требует O(2^n) времени), тогда как моя единственная рекурсия является линейной (то есть O(n)). Кроме того, числа Фибоначчи имеют удобное свойство, которое допускает логарифмическую рекурсивную реализацию , т.е. занимает O(log(n)) время.

Получить все числа до n в списке

Если вам нужны все числа вплоть до n-го, вам нужен простой цикл: 

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

Если вы настаиваете на рекурсии: 

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

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

Можно, конечно, создать хвостовую рекурсивную версию: 

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