재귀

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에서 재귀 람다 함수를 작성하는 방법은 무엇입니까?

감사합니다.

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 시나리오를 처리합니다. a와 b에 만약 사용자가 제공 값을,이 값이 0이 아닌 1 인 경우에, 당신은 늘 당신의 대안으로 그레이엄의 alambda을 사용할 수 있습니다 정답

Answer 3

를 얻을 : 당신은 (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)) 

또는 ... 당신은 조금 다른 문제를 볼 수 있었다 : 사용 노르 빅의 defun-memo 매크로 (자동 메모이 제이션) 및 FIB의 비 꼬리 재귀 버전, 아무튼 FIB 함수를 정의하는 도우미 기능이 필요하다 할지라도, 피임약 밀착에 대한 수학적 묘사를보다 직접적으로 표현합니다. nce 및 (필자는) 최소한 tail 재귀 버전만큼 효율적이며 여러 호출 후에는 tail-recursive 버전보다 훨씬 효율적입니다.

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