遞歸在lambda函數

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中編寫遞歸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

你可以嘗試這樣的事情，以及

(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，你不會得到正確的答案

Answer 3

你可以用格雷厄姆的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)) 

或者......你可以看看這個問題有點不同：使用弱勢族羣的defun-memo宏（自動記憶化），和FIB的非尾遞歸版本，定義沒有按一個FIB功能甚至不需要輔助函數，更直接地表達了fib seque的數學描述nce和（我認爲）至少和尾遞歸版本一樣高效，並且在多次調用之後，變得比尾遞歸版本更有效。

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