再帰は、ラムダ関数

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で再帰ラムダ関数を書くのですか？

ありがとうございました。

Answer 1

LETは、式を評価するために同じ囲む環境を使用して、同時に変数を概念的にバインドします。

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

の長所を試すことができます：また、関数の名前空間内のシンボルf0とf1を結合する、代わりにLABELSを使用してラッパーを構築する必要はありません関数。 Condコンストラクトはif-then-elseifシナリオを処理します。ユーザ供給値の場合とB、及びこれらの値は0と1でない場合、あなたは文句を言わない、正しい答えを得る

Answer 3

あなたはの代替としてグラハムのalambdaを使用することができます：あなたは(fib-r 10) => 55

短所としてREPLでこのメソッドを呼び出し、ラベル：

(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の非末尾再帰バージョンは、doesnのFIB関数を定義しますヘルパー関数を必要とする場合もありますが、フィブスシークの数学的記述をより直接的に表現しますnce、（私は思うが）少なくとも、tail再帰バージョンと同じくらい効率的で、複数の呼び出しの後では、tail-recursiveバージョンよりもさらに効率的になります。

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