Recursing in a lambda function

Question

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.

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

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