CODEWITHSUNDEEP
recursionfunctional-programmingclojurelisptail-recursion
Sonia Hamilton
Sonia Hamilton

Reputation: 4419

How to do recursion in anonymous fn, without tail recursion

How do I do recursion in an anonymous function, without using tail recursion?

For example (from Vanderhart 2010, p 38):

(defn power
  [number exponent]
  (if (zero? exponent)
    1
    (* number (power number (- exponent 1)))))

Let's say I wanted to do this as an anonymous function. And for some reason I didn't want to use tail recursion. How would I do it? For example:

( (fn [number exponent] ......))))) 5 3)
125

Can I use loop for this, or can loop only be used with recur?

Upvotes: 22

Views: 8288

Answers (5)

Jeremy
Jeremy

Reputation: 22435

The fn special form gives you the option to provide a name that can be used internally for recursion.

(doc fn)
;=> (fn name? [params*] exprs*)

So, add "power" as the name to complete your example.

(fn power [n e]
  (if (zero? e)
    1
    (* n (power n (dec e)))))

Even if the recursion happened in the tail position, it will not be optimized to replace the current stack frame. Clojure enforces you to be explicit about it with loop/recur and trampoline.

Upvotes: 50

Óscar López
Óscar López

Reputation: 236142

I know that in Clojure there's syntactic support for "naming" an anonymous function, as other answers have pointed out. However, I want to show a first-principles approach to solve the question, one that does not depend on the existence of special syntax on the programming language and that would work on any language with first-order procedures (lambdas).

In principle, if you want to do a recursive function call, you need to refer to the name of the function so "anonymous" (i.e. nameless functions) can not be used for performing a recursion ... unless you use the Y-Combinator. Here's an explanation of how it works in Clojure.

Let me show you how it's used with an example. First, a Y-Combinator that works for functions with a variable number of arguments:

(defn Y [f]
  ((fn [x] (x x))
   (fn [x]
       (f (fn [& args]
              (apply (x x) args))))))

Now, the anonymous function that implements the power procedure as defined in the question. Clearly, it doesn't have a name, power is only a parameter to the outermost function:

(fn [power]
      (fn [number exponent]
          (if (zero? exponent)
              1
              (* number (power number (- exponent 1))))))

Finally, here's how to apply the Y-Combinator to the anonymous power procedure, passing as parameters number=5 and exponent=3 (it's not tail-recursive BTW):

((Y 
  (fn [power]
      (fn [number exponent]
          (if (zero? exponent)
              1
              (* number (power number (- exponent 1)))))))
 5 3)

> 125

Upvotes: 18

BillRobertson42
BillRobertson42

Reputation: 12883

loop can be a recur target, so you could do it with that too.

Upvotes: 0

Arthur Ulfeldt
Arthur Ulfeldt

Reputation: 91607

Yes you can use loop for this. recur works in both loops and fns 

user> (loop [result 5 x 1] (if (= x 3) result (recur (* result 5) (inc x))))
125

an idomatic clojure solution looks like this:

user> (reduce * (take 3 (repeat 5)))
125

or uses Math.pow() ;-)

user> (java.lang.Math/pow 5 3)
125.0

Upvotes: 3

gregspurrier
gregspurrier

Reputation: 1458

fn takes an optional name argument that can be used to call the function recursively.

E.g.:

user> ((fn fact [x]
           (if (= x 0)
               1
               (* x (fact (dec x)))))
       5)
;; ==> 120

Upvotes: 4

Related Questions