Fibonacci Sequence using loop and recur

Question

I am doing the Project Euler challenge in Clojure and I want to find the sum of all the even numbers in a fibonacci sequence up to a certain number.

The code for a function that does this is below. I know there are quicker and easier ways of doing this, I am just experimenting with recursion using loop and recur. However the code doesn't seem to work it never returns an answer.

(defn fib-even-sum [upto]
  (loop [previous 1 nxt 1 sum 0]
    (if (or (<= upto 1) (>= nxt upto))
     sum)
    (if (= (mod nxt 2) 0)
       (recur nxt (+ previous nxt) (+ sum nxt))
       (recur nxt (+ previous nxt) sum))))

I was not sure if I could do recur twice in the same loop or not. I'm not sure if this is causing the problem?

I was looking into that predicate. I'm going to change the code to use it. Thanks for pointing it out. — adamjmarkham
– adamjmarkham, Commented Jun 23, 2011 at 13:54
there is a fibs in 'clojure.contrib.lazy-seqs which is quite fast. With that, the problem can be expressed like this: (reduce + (filter #(even? %) (take-while #(< % 4000000) (fibs)))) .. some of the other Euler Problems can be done as one-liners as well, enjoy! :-) — klang
– klang, Commented Jun 24, 2011 at 18:24
Just an alternative (know you weren't looking for one, so it's in a comment!) (def fibo (map second (iterate (fn [[x y]] [y (+ x y)]) [0 1]))) — Isaac
– Isaac, Commented Jun 25, 2011 at 23:46
@IsaacHodes Yikes, don't do that. If you def it at the top-level, it can never get GCed. Instead, (defn fib0 [] (map ...)) and call fib0 whenever you need a new copy of the sequence. — amalloy
– amalloy, Commented Nov 27, 2011 at 23:55

Paul Lam · Accepted Answer · 2011-06-23 13:43:57Z

5

You have a misplaced closing paren in the first IF (after sum)...

(defn fib-even-sum [upto]
  (loop [previous 1 nxt 1 sum 0]
    (if (or (<= upto 1) (>= nxt upto))
        sum
        (if (= (mod nxt 2) 0)
           (recur nxt (+ previous nxt) (+ sum nxt))
           (recur nxt (+ previous nxt) sum)))))

Now it works and fast

edited Jun 23, 2011 at 13:43

answered Jun 23, 2011 at 13:37

Paul Lam

1,8192 gold badges16 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

adamjmarkham Over a year ago

Thanks. I see the problem. Works great now.

amalloy Over a year ago

This is a common problem for new lisp coders, by the way. If I were writing this, I'd replace the (if a x (if b y z)) pattern with a use of cond: (cond a x, b y, :else z). But of course you should learn at your own pace, and not worry about form if you're still learning the function.

Collectives™ on Stack Overflow

Fibonacci Sequence using loop and recur

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related