Recursing in a lambda function

问题:

I have the following 2 functions that I wish to combine into one:

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

I would like to have just one function, so I tried something like this:

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

however this is not working. The exact error is *** - IF: variable F1 has no value I'm a beginner as far as LISP goes, so I'd appreciate a clear answer to the following question: how do you write a recursive lambda function in lisp?

Thanks.

回答1:

LET conceptually binds the variables at the same time, using the same enclosing environment to evaluate the expressions. Use LABELS instead, that also binds the symbols f0 and f1 in the function 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)))

回答2:

You can use Graham's alambda as an alternative to labels:

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

Or... you could look at the problem a bit differently: Use Norvig's defun-memo macro (automatic memoization), and a non-tail-recursive version of fib, to define a fib function that doesn't even need a helper function, more directly expresses the mathematical description of the fib sequence, and (I think) is at least as efficient as the tail recursive version, and after multiple calls, becomes even more efficient than the tail-recursive version.

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

回答3:

You can try something like this as well

(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: You don't have to build a wrapper function. Cond constructt takes care of if-then-elseif scenarios. You call this on REPL as (fib-r 10) => 55

Cons: If user supplies values to a and b, and if these values are not 0 and 1, you wont get correct answer