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
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
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
@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

Paul Lam Paul Lam · Accepted Answer · 2011-06-23T13:37:20

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

Fibonacci Sequence using loop and recur

1 Answers