How to write this Clojure function so that it does not delete the stack?

Question

I am new to Clojure, and I think my approach to writing code still does not match the Clojure Way. At least I keep writing functions that lead to StackOverflow errors with large values. I learned about using recur, which was a good step forward. But how to make functions like the ones below for values ​​like 2500000?

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

The function, in my opinion, is a “simple” implementation of the Fibonacci generator. I have seen other implementations that are much more optimized, but less obvious in terms of what they do. That is, when you read the definition of a function, you don’t go “oh, fibonacci”.

Any pointers would be greatly appreciated!

Answer 1

You need a mental model of your function. Let's say that you perform your function on your own, using scraps of paper for each call. 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 mark this and start two new trims. You cannot drop the first because you still have things to do when you finish other calculations. You can imagine that this calculation will require a lot of trimmings.

Another way is not to start from above, but below. How do you do it manually? You start with the first numbers, 1, 1, 2, 3, 5, 8 & hellip ;, and then always add the last two until you do it i times. You can even throw away all the numbers except the last two at each step so that you can reuse most of the crop.

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

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

Thinking "how I will do it step by step on paper" often leads to good implementation.

Answer 2

The Fibonacci generator, implemented in a "simple" way, as in the definition of a sequence, will always remove your stack up. None of the two recursive calls to fib is tail recursive; such a definition cannot be optimized.

Unfortunately, if you want to write an effective implementation that works for large numbers, you have to accept the fact that mathematical notation does not convert the code as cleanly as we would like.

For example, a non-recursive implementation can be found in clojure.contrib.lazy-seqs . A number of different approaches to this problem can be found on the Haskell wiki . This should not be difficult to understand with a basic understanding of functional programming.

Answer 3

  ;;from "The Pragmatic Programmers Programming Clojure" (defn fib [] (map first (iterate (fn [[ab]][b (+ ab)])[0N 1N]))) (nth (fib) 2500000)