recursing trong một hàm lambda

Question

Tôi có 2 chức năng sau mà tôi muốn kết hợp thành một:

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

Tôi muốn chỉ có một chức năng, vì vậy tôi cố gắng một cái gì đó như thế này:

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

tuy nhiên điều này không hoạt động. Lỗi chính xác là *** - IF: variable F1 has no value Tôi là một người mới bắt đầu theo như LISP đi, vì vậy tôi đánh giá cao một câu trả lời rõ ràng cho câu hỏi sau: làm thế nào để bạn viết một hàm lambda đệ quy trong lisp?

Cảm ơn.

Answer 1

LET liên kết khái niệm các biến cùng một lúc, sử dụng cùng một môi trường kèm theo để đánh giá các biểu thức. Sử dụng LABELS thay vào đó, mà cũng liên kết với những biểu tượng f0 và f1 trong hàm namespace:

(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

Bạn có thể thử một cái gì đó như thế này cũng

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

Ưu điểm: Bạn không cần phải xây dựng một wrapper chức năng. Cond constructt sẽ xử lý các kịch bản if-then-elseif. Bạn gọi đây trên REPL như (fib-r 10) => 55

Nhược điểm: Nếu nguồn cung cấp sử dụng các giá trị cho a, b, và nếu những giá trị không phải là 0 và 1, bạn sẽ không nhận được câu trả lời đúng

Answer 3

Bạn có thể sử dụng Graham alambda như một thay thế cho nhãn:

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

Hoặc ... bạn có thể xem xét vấn đề một chút khác nhau: Sử dụng Norvig defun-memo vĩ mô (tự động memoization), và một phiên bản không-đuôi-đệ quy của fib, để xác định một hàm fib điều đó không thậm chí không cần một hàm trợ giúp, trực tiếp thể hiện mô tả toán học của fib seque nce, và (tôi nghĩ) ít nhất cũng hiệu quả như phiên bản đệ quy đuôi, và sau nhiều cuộc gọi, thậm chí còn hiệu quả hơn phiên bản đệ quy đuôi.

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