Lazy sequence or recur for mathematical power function?

Question

As an exercise I implemented the mathematical power function. Once using recur:

(defn power [a n]
  (let [multiply (fn [x factor i]
                   (if (zero? i)
                     x
                     (recur (* x factor) factor (dec i))))]
  (multiply a a (dec n))))

user=> (time (dotimes [_ 10000] (power 2 512)))
"Elapsed time: 1839.406746 msecs"

And once with lazy-seq:

(defn power [a n]
  (letfn [(multiply [a factor]
            (lazy-seq
              (cons a (multiply (* a factor) factor))))]
  (nth (multiply a a) (dec n))))

user=> (time (dotimes [_ 10000] (power 2 512)))
"Elapsed time: 2162.297827 msecs"

Which implementation do you think is superior? I truly have no idea.. (I'd use recur because it's easier to understand.)

I read that lazy-seq is fast because it uses internal caching. But I don't see any opportunities for caching in my sample. Am I overlooking something?

Update
I posted the timings with the samples. It seems that recur is slightly faster here.

Regular recursion doesn't do too bad either:

(defn power [a n]
   (if (== n 1)
      a
      (* a (power a (dec n)))))

user=> (time (dotimes [_ 10000] (power 2 512)))
"Elapsed time: 1877.34521 msecs"

Answer 1

Recursion re-uses stack, which is typically quite fast and small. I don't see how lazy-seq can be faster.

Answer 2

You should do timing tests, run both 1m times and see the times. Usually non recursive functions are faster, but when dealing with functional languages recursion is the preferred way to go, as they usually use tail calls. Clojure in based on Java Clr so I don't now if the tail call is supported, but if it is it should be just as fast as non recursive call.

Answer 3

First of all, the usual advice is to pick the correct algorithm first, worry about implementation details later (if your code is actually that sensitive to performance or might be used in contexts which are).

Then there are aesthetic considerations. The loop / recur seems cleaner to me, just because it's the perfectly natural way to go about the problem. Using sequences makes sense when they enter the semantic picture somehow or, failing that, make the code significantly easier to write / understand / make performant. Nothing of the sort is the case here.

Finally, I'd definitely expect loop / recur to be faster overall, if only because it avoids the unnecessary allocation & GC. Initial timings support this. There is indeed no opportunity to benefit from any sort of caching here, because you generate your sequence from scratch whenever power is called and never hold on to it after returning.

Answer 4

I provided some lazy power functions of my own here to show how you can re-use a lazy-seq from a function.

Every time you call my-simple-lazy-power with two numbers, it builds a lazy seq with powers of a certain number x and returns the nth item of it. Using this version is very expensive because it constructs exactly one lazy-seq for each function call. This is probably why the benchmark for my-simple-lazy-power is so darn slow. Since lazy-seqs cache their results you probably want to re-use them. This is what my-lazy-power does: it constructs a lazy-seq for a number x and wraps a function around it which accepts n as an argument. You can re-use the latter function to access the cached results. (The function keeps a reference to the lazy-seq as long as the function exists, because it 'closed over' the lazy-seq. That is why they call it a closure.)

Another common way to cache results of a function is to use a memoized version of the function. Basically memoize memorizes the result for the arguments you pass in, so next time you pass in the exact same arguments, it will return the result from cache. See examples below. For comparison I timed your versions and their memoized versions also.

(defn my-simple-lazy-power [x n]
  (let [my-lazy-list 
    ((fn my-lazy [y] 
       (lazy-cat [y] (map #(* % x) (my-lazy y)))) x)]
    (nth my-lazy-list n)))

(defn my-lazy-power [x]
  (let [my-lazy-list 
    ((fn my-lazy [y] 
       (lazy-cat [y] (map #(* % x) (my-lazy y)))) x)]
    (fn [n]
      (nth my-lazy-list n))))

(defn rec-power [a n]
  (let [multiply (fn [x factor i]
                   (if (zero? i)
                     x
                     (recur (* x factor) factor (dec i))))]
    (multiply a a (dec n))))

(defn lazy-power [a n]
  (letfn [(multiply [a factor]
            (lazy-seq
             (cons a (multiply (* a factor) factor))))]
    (nth (multiply a a) (dec n))))

(def mem-my-simple-power (memoize my-simple-lazy-power))
(def mem-my-power (memoize my-lazy-power))
(def mem-rec-power (memoize rec-power))
(def mem-laz-power (memoize lazy-power))

(time (dotimes [_ 50] (my-simple-lazy-power 2 512)))
"Elapsed time: 7138.346976 msecs"
nil

(time (let [my-pow-2 (my-lazy-power 2)]
  (dotimes [_ 10000] (my-pow-2 512))))
"Elapsed time: 854.717301 msecs"
nil

(time (dotimes [_ 10000] (rec-power 2 512)))
"Elapsed time: 2726.559879 msecs"
nil

(time (dotimes [_ 10000] (mem-rec-power 2 512)))
"Elapsed time: 4.775677 msecs"
nil

(time (dotimes [_ 10000] (lazy-power 2 512)))
"Elapsed time: 3617.100209 msecs"
nil

(time (dotimes [_ 10000] (mem-laz-power 2 512)))
"Elapsed time: 4.95887 msecs"
nil

PS: I had to write fn around the lazy-seq definition in my versions, because let does not support recursive definitions, but fn does.

PS2: sorry for the indentation, copy pasting from Emacs doesn't seem to preserve it...