2

I'm trying to solve Project Euler question 2 with Lisp. This recursive solution blows the stack on execution, but I thought Lisp (using clisp) would recognize the tail recursion. This is being entered into the top-level.

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"

   (if (> f2 4000000) sum)
   (e2-problem f2 (+ f1 f2) (if (evenp f2) 
                                (+ sum f2) 
                               sum))

Is my implementation not correctly arranged for optimization? I imagine this would hinder my Lisp education quite a bit if I could not rely on idiomatic recursion.

Rainer Joswig
  • 136,269
  • 10
  • 221
  • 346
Casey D.
  • 23
  • 2

4 Answers4

9

Recursion (or even iteration) is not necessary!

Every third Fibonacci number is even:

1 1 2 3 5 8 13 21 34 55 89 144 ...

and since each even Fibonacci number (in bold) is the sum of the two preceding odd Fibonacci numbers, the sum of the even Fibonacci numbers up to Fn is exactly half of the sum of all the Fibonacci numbers up to Fn (if Fn is even, of course).

Now, the sum of the first n Fibonacci numbers is Fn+2 − 1. This is easy to check by induction: the sum of the first n + 1 Fibonacci numbers is F1 + F2 + ... + Fn + Fn+1, which equals Fn+2 − 1 + Fn+1 by hypothesis, which equals Fn+3 − 1 by the definition of the Fibonacci numbers.

So if you can find the largest N such that F3N ≤ 4,000,000, then the sum that’s asked for will be (F3N+2 − 1) / 2.

(I'll leave the remaining details to you but it should be straightforward from here.)

Gareth Rees
  • 64,967
  • 9
  • 133
  • 163
  • Interesting! So i guess it comes down to the best way to numerically solve the Binet equation: 4 million = (φ^x-(-1/φ)^x)/√5 My first thought is Newton's method - any better ways? – Nick Alger Dec 05 '10 at 03:14
  • 1
    You don't need Newton's method: just observe that (1/φ)^x is very small. – Gareth Rees Dec 05 '10 at 11:14
4

I thought Lisp (using clisp) would recognize the tail recursion

For an environment to implement tail call elimination is mandatory in Scheme, but not in most other Lisp dialects, such as Common Lisp.

Ken
  • 9,797
  • 3
  • 16
  • 14
  • 1
    Specifically clisp does not optimize tail calls (I thought there was an option to enable, but I can't find it in the manpage), while e.g. sbcl does. – sepp2k Dec 03 '10 at 23:00
  • 1
    if it would recognize tail recursion, the example would run forever - without blowing the stack. As an endless loop, since it does not terminate. Well, a number would overflow. – Rainer Joswig Dec 04 '10 at 01:47
  • I see many people saying the code does not terminate. Why doesn't it terminate due to the if statement? – Casey D. Dec 04 '10 at 17:09
  • The `if` ends, and then the next line calls `e2-problem` regardless of what happened there. – Ken Dec 04 '10 at 18:33
  • Thank you. I thought Lisp would return result of the first form, but that makes no sense. It returns the last! – Casey D. Dec 04 '10 at 20:55
4

1) Correct syntax error in code: 

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"
   (if (> f2 4000000) 
       sum   ;; here was a closing bracket 
       (e2-problem f2 (+ f1 f2) (if (evenp f2) 
                                    (+ sum f2) 
                                    sum))))  ;; 2 more brackets here

2) use SBCL. CLISP is not kind enough to detect tail recursion.

3) use highest available optimization level:

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"
   (declare (optimize (debug 0)))  ;; optimization
   ...
ffriend
  • 27,562
  • 13
  • 91
  • 132
  • 1
    Ooops! DEBUG 0, of course. And yes, this is not complete optimization, but it tells to runtime that it may eliminate stack frames, i.e. allow tail recursion. – ffriend Dec 04 '10 at 04:36
  • 1
    CLISP does detect tail recursion. – sds Apr 14 '14 at 19:28
2

Your code implements an endless loop. It does not terminate.

Using LOOP:

(defun e2-problem-a (n)
  "Sum fibonacci sequence, even terms up to n"
  (loop for f1 = 1 then f2
        and f2 = 1 then (+ f1 f2)
        while (<= f2 n)
        when (evenp f2) sum f2))
Rainer Joswig
  • 136,269
  • 10
  • 221
  • 346