在lambda函数中递归

Question

我有以下两个功能,我希望合并为一个:

(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写递归lambda函数？

谢谢.

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

您可以使用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宏（自动记忆）和非尾部递归的fib版本，以定义甚至不需要帮助函数的fib函数，更直接地表达了fib序列的数学描述，并且（我认为）至少与尾部递归版本一样有效，并且在多次调用之后，它变得比尾部递归版本更加有效。

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