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

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

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

Спасибо.

Ответы

Ответ 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)))

Ответ 2

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

(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

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

Ответ 3

Вы можете использовать Graham 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 defun-memo macro (автоматическая memoization), а не -tail-recursive version of fib, чтобы определить функцию fib, которая даже не нуждается в вспомогательной функции, более прямо выражает математическое описание последовательности фибонов и (я думаю) не менее эффективна, как хвостовая рекурсивная версия, и после нескольких вызовов становится еще более эффективным, чем хвостовая рекурсивная версия.

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