How do I write this Clojure function so that it doesn't blow out the stack?

Question

I'm new to Clojure and I think my approach to writing code so far is not in line with the "Way of Clojure". At least, I keep writing functions that keep leading to StackOverflow errors with large values. I've learned about using recur which has been a good step forward. But, how to make functions like the one below work for values like 2500000?

(defn fib [i]
  (if (>= 2 i)
    1
    (+ (fib (dec i))
       (fib (- i 2)))))

The function is, to my eyes, the "plain" implementation of a Fibonacci generator. I've seen other implementations that are much more optimized, but less obvious in terms of what they do. I.e. when you read the function definition, you don't go "oh, fibonacci".

Any pointers would be greatly appreciated!

Answer 1

You need to have a mental model of how your function works. Let's say that you execute your function yourself, using scraps of paper for each invocation. First scrap, you write (fib 250000), then you see "oh, I need to calculate (fib 249999) and (fib 249998) and finally add them", so you note that and start two new scraps. You can't throw away the first, because it still has things to do for you when you finish the other calculations. You can imagine that this calculation will need a lot of scraps.

Another way is not to start at the top, but at the bottom. How would you do this by hand? You would start with the first numbers, 1, 1, 2, 3, 5, 8 …, and then always add the last two, until you have done it i times. You can even throw away all numbers except the last two at each step, so you can re-use most scraps.

(defn fib [i]
  (loop [a 0
         b 1
         n 1]
    (if (>= n i)
        b
        (recur b
               (+ a b)
               (inc n)))))

This is also a fairly obvious implementation, but of the how to, not of the what. It always seems quite elegant when you can simply write down a definition and it gets automatically transformed into an efficient calculation, but programming is that transformation. If something gets transformed automatically, then this particular problem has already been solved (often in a more general way).

Thinking "how would I do this step by step on paper" often leads to a good implementaion.

Answer 2

A Fibonacci generator implemented in a "plain" way, as in the definition of the sequence, will always blow your stack up. Neither of two recursive calls to fib are tail recursive, such definition cannot be optimised.

Unfortunately, if you'd like to write an efficient implementation working for big numbers you'll have to accept the fact that mathematical notation doesn't translate to code as cleanly as we'd like it to.

For instance, a non-recursive implementation can be found in clojure.contrib.lazy-seqs. A whole range of various approaches to this problem can be found on Haskell wiki. It shouldn't be difficult to understand with knowledge of basics of functional programming.