Рекурсивный в лямбда-функции

Question

У меня есть следующие 2 функции, которые я хочу объединить в одну:

(defun fib (n)
  (if (= n 0) 0 (fib-r n 0 1)))

(defun fib-r (n a b)
  (if (= n 1) b (fib-r (- n 1) b (+ a b))))

Я хотел бы иметь только одну функцию, поэтому я попробовал что-то вроде этого:

(defun fib (n)
  (let ((f0 (lambda (n) (if (= n 0) 0 (funcall f1 n 0 1))))
        (f1 (lambda (a b n) (if (= n 1) b (funcall f1 (- n 1) b (+ a b))))))
    (funcall f0 n)))

Однако это не работает.Точная ошибка: *** - IF: variable F1 has no value Я новичок в LISP, поэтому я был бы признателен за четкий ответ на следующий вопрос: как написать рекурсивную лямбда-функцию в lisp?

Спасибо.

Answer 1

LET концептуально связывает переменные одновременно, используя одну и ту же окружающую среду для оценки выражений.Вместо этого используйте LABELS, который также связывает символы f0 и f1 в пространстве имен функции:

(defun fib (n)
  (labels ((f0 (n) (if (= n 0) 0 (f1 n 0 1)))
           (f1 (a b n) (if (= n 1) b (f1 (- n 1) b (+ a b)))))
    (f0 n)))

Answer 2

Вы можете использовать alambda Грэма в качестве альтернативы ярлыкам:

(defun fib (n)
  (funcall (alambda (n a b)
             (cond ((= n 0) 0)
                   ((= n 1) b)
                   (t (self (- n 1) b (+ a b))))) 
           n 0 1)) 

Или ... вы могли бы взглянуть на проблему немного иначе: используйте Norvig's defun-макрос memo (автоматическое запоминание) и нерекурсивно-рекурсивная версия fib для определения функции fib, которой даже не требуется вспомогательная функция, более прямо выражает математическое описание последовательности fib, и (Iдумаю) по крайней мере так же эффективна, как хвостовая рекурсивная версия, и после нескольких вызовов становится еще более эффективной, чем хвостовая рекурсивная версия.

(defun-memo fib (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (+ (fib (- n 1))
              (fib (- n 2))))))

Answer 3

Вы также можете попробовать что-то вроде этого

(defun fib-r (n &optional (a 0) (b 1) )
  (cond
    ((= n 0) 0)
    ((= n 1) b)
    (T (fib-r (- n 1) b (+ a b)))))

Плюсы: Вам не нужно создавать функцию-оболочку.Cond constructt заботится о сценариях if-then-elseif.Вы называете это в REPL как (fib-r 10) => 55

Минусы: если пользователь вводит значения a и b, и если эти значения не равны 0 и 1, вы не получите правильный ответ