The lisp-way to solve Fibonnaci

Question

I wanted to try and learn Lisp, but I very quickly gave up. I figured I'd try again. I'm looking at Problem 2 on Project Euler - finding the sum of all even Fibonacci numbers under 4 Million.

I wrote the following code which works, but is all kinds of ugly. Chief among them is the fact that it's so slow - because it's doing naive recursion all the time.

When I wrote this program in Python I built up a list as I calculated and never recalculated numbers. I know I could do that here (somehow) but that doesn't seem to be true to the spirit of lisp, of functional programming. I gave up after #3, when I hit a recursion depth limit and had to rewrite my code to use a loop instead of recursion.

So I suppose my questions are:

1. What's the 'right, lispy way' to solve this problem?
2. How do you reconcile recursion and the notion of 'just calculating everything' with the practical limit of calculating everything?
3. Any recommendations for learning lisp besides The Little Schemer, and Project Euler?

And here's my code:

 (defun fib(i)
   (if (= i 1)                   ;Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2))))))

 (defun solve(i)
   (let ((f (fib i)))            ;Store result in local variable
     (print f)                   ;For debugging
     (if (< 4000000 f)
       0                         ;return
       (if (= 0 (mod f 2))
         (+ f (solve (+ i 1)))   ;add number
         (solve (+ i 1))))))     ;don't

 (print (solve 1))

Answer 1

Use tail recursion instead of naive recursion. Most Lisp implementations should perform the tailcall-optimization; no more recursion depth limit.

Beyond that, try to think of things in terms of lists and abstract operations you could perform on those lists. Two of the more relevant operations to consider:

• filter
• fold

Regarding other Lisp resources:

• Common Lisp—On Lisp
• Scheme—Structure and Interpretation of Computer Programs

UPDATE: Tail-recursive Scheme fib function:

(define (fib n)
  (fib-tr n 1 0))

(define (fib-tr n next result)
  (cond ((= n 0) result)
        (else (fib-tr (- n 1) (+ next result) next))))