Menu
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?
216
Anonymous recursion primarily consists of calling "the current function", which results in direct recursion. Anonymous indirect recursion is possible, such as by calling "the caller (the previous function)", or, more rarely, by going further up the call stack, and this can be chained to produce mutual recursion.
Non-Tail / Head Recursion A function is called the non-tail or head recursive if a function makes a recursive call itself, the recursive call will be the first statement in the function. It means there should be no statement or operation is called before the recursive calls.
The tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to optimize the code. When one function is called, its address is stored inside the stack. So if it is tail recursion, then storing addresses into stack is not needed.
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.
101
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 If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
