manera recursiva en una función lambda

Question

tengo los siguientes 2 funciones que desea combinar en una sola:

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

me gustaría tener sólo una función, por lo que intentó hacer algo como esto:

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

sin embargo, esto no está funcionando. El error exacto es *** - IF: variable F1 has no value Soy un principiante en lo que respecta a LISP, por lo que agradecería una respuesta clara a la siguiente pregunta: ¿cómo se escribe una función lambda recursiva en lisp?

Gracias.

Answer 1

LET vincula conceptualmente las variables al mismo tiempo, utilizando el mismo entorno envolvente para evaluar las expresiones. Utilice LABELS en cambio, que también se une a los símbolos f0f1 y en la función de espacio de nombres:

(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

Usted puede intentar algo como esto, así

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

Pros: Usted no tiene que construir un envoltorio función. Cond constructt se ocupa de los escenarios if-then-elseif. Se llama a esto en REPL como (fib-r 10) => 55

Contras: si los valores de usuario suministra a A y B, y si estos valores no son 0 y 1, no vas a encontrar respuesta correcta

Answer 3

Puede utilizar Graham alambda como una alternativa a etiquetas:

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

O ... usted podría mirar el problema un poco diferente: uso de defun-memo macro (memoization automática) una versión no recursiva de cola de fib Norvig, y, para definir una función fib que doesn incluso necesita una función auxiliar, expresa más directamente la descripción matemática de la fibsecuencia nce, y (creo) es al menos tan eficiente como la versión recursiva de cola, y después de múltiples llamadas, se vuelve incluso más eficiente que la versión recursiva de cola.

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