javascript: recursive anonymous function?

Question

Let's say I have a basic recursive function:

function recur(data) {
    data = data+1;
    var nothing = function() {
        recur(data);
    }
    nothing();
}

How could I do this if I have an anonymous function such as...

(function(data){
    data = data+1;
    var nothing = function() {
        //Something here that calls the function?
    }
    nothing();
})();

I'd like a way to call the function that called this function... I've seen scripts somewhere (I can't remember where) that can tell you the name of a function called, but I can't recall any of that information right now.

Splenectomy

@thenduks: For the same reason why one would use an anonymous function. Just that sometimes recursion is necessary. – Armidaarmiger

It's a shame arguments.callee exists, and this functnio doesn't do anything useful. I was looking up Y combinator :P . Damn, that stuff will never get useful... – Chemoprophylaxis

Yep, as Kobi linked, use a fixed point combinator such as Y to do anonymous recursive functions without arguments.callee. – Inflectional

See w3future.com/weblog/stories/2002/02/22/… for an example of the Y combinator in JS. – Inflectional

It's done by Y-Combinator in functional languages. For detailed explanation have a look at this – Bellow

Answer 1

You can give the function a name, even when you're creating the function as a value and not a "function declaration" statement. In other words:

(function foo() { foo(); })();

is a stack-blowing recursive function. Now, that said, you probably don't may not want to do this in general because there are some weird problems with various implementations of Javascript. (note — that's a fairly old comment; some/many/all of the problems described in Kangax's blog post may be fixed in more modern browsers.)

When you give a name like that, the name is not visible outside the function (well, it's not supposed to be; that's one of the weirdnesses). It's like "letrec" in Lisp.

As for arguments.callee, that's disallowed in "strict" mode and generally is considered a bad thing, because it makes some optimizations hard. It's also much slower than one might expect.

edit — If you want to have the effect of an "anonymous" function that can call itself, you can do something like this (assuming you're passing the function as a callback or something like that):

asyncThingWithCallback(params, (function() {
  function recursive() {
    if (timeToStop())
      return whatever();
    recursive(moreWork);
  }
  return recursive;
})());

What that does is define a function with a nice, safe, not-broken-in-IE function declaration statement, creating a local function whose name will not pollute the global namespace. The wrapper (truly anonymous) function just returns that local function.

Stoichiometric

Can we avoid polluting the global namespace another way with ES5 sctrict (I haven't read deep into ES5 yet)? – Splenectomy

@pointy can you please look at this questing. #27473950 – Christa

I guess it's not possible to use (() => { call_recursively_self_here() })() and call itself recursively, right? I must give it a name. – Calv

@Calv well you could do something like the last example in my answer. Bind the arrow function to a local variable in a wrapper function so that your arrow function can refer to itself with the variable name. The wrapper would then return the variable (which refers to the arrow function). – Stoichiometric

In your answer your function (recursive) call itself by name so in fact it is not anonymous recursive function. But user633183 shows (here) that this is possible. – Newcastle

@KamilKiełczewski that's a fine answer, but it's kind-of pointless; there's no harm in giving functions names. – Stoichiometric

@Stoichiometric but OP ask about this. In theoretical point of view this is interesting question. – Newcastle

@KamilKiełczewski I agree that it's extremely interesting, but it would be a fairly strange decision to implement recursion that way in code intended for some real-world application. – Stoichiometric

@Stoichiometric maybe some hackers will find application ;) – Newcastle

Answer 2

U combinator

By passing a function to itself as an argument, a function can recur using its parameter instead of its name! So the function given to U should have at least one parameter that will bind to the function (itself).

In the example below, we have no exit condition, so we will just loop indefinitely until a stack overflow happens

const U = f => f (f) // call function f with itself as an argument

U (f => (console.log ('stack overflow imminent!'), U (f)))

We can stop the infinite recursion using a variety of techniques. Here, I'll write our anonymous function to return another anonymous function that's waiting for an input; in this case, some number. When a number is supplied, if it is greater than 0, we will continue recurring, otherwise return 0.

const log = x => (console.log (x), x)

const U = f => f (f)

// when our function is applied to itself, we get the inner function back
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
// returns: (x => x > 0 ? U (f) (log (x - 1)) : 0)
// where f is a reference to our outer function

// watch when we apply an argument to this function, eg 5
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0) (5)
// 4 3 2 1 0

What's not immediately apparent here is that our function, when first applied to itself using the U combinator, it returns a function waiting for the first input. If we gave a name to this, can effectively construct recursive functions using lambdas (anonymous functions)

const log = x => (console.log (x), x)

const U = f => f (f)

const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)

countDown (5)
// 4 3 2 1 0

countDown (3)
// 2 1 0

Only this isn't direct recursion – a function that calls itself using its own name. Our definition of countDown does not reference itself inside of its body and still recursion is possible

// direct recursion references itself by name
const loop = (params) => {
  if (condition)
    return someValue
  else
    // loop references itself to recur...
    return loop (adjustedParams)
}

// U combinator does not need a named reference
// no reference to `countDown` inside countDown's definition
const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)

---

How to remove self-reference from an existing function using U combinator

Here I'll show you how to take a recursive function that uses a reference to itself and change it to a function that employs the U combinator to in place of the self reference

const factorial = x =>
  x === 0 ? 1 : x * factorial (x - 1)
  
console.log (factorial (5)) // 120

Now using the U combinator to replace the inner reference to factorial

const U = f => f (f)

const factorial = U (f => x =>
  x === 0 ? 1 : x * U (f) (x - 1))

console.log (factorial (5)) // 120

The basic replacement pattern is this. Make a mental note, we will be using a similar strategy in the next section

// self reference recursion
const foo =         x => ...   foo (nextX) ...

// remove self reference with U combinator
const foo = U (f => x => ... U (f) (nextX) ...)

---

Y combinator

related: the U and Y combinators explained using a mirror analogy

In the previous section we saw how to transform self-reference recursion into a recursive function that does not rely upon a named function using the U combinator. There's a bit of an annoyance tho with having to remember to always pass the function to itself as the first argument. Well, the Y-combinator builds upon the U-combinator and removes that tedious bit. This is a good thing because removing/reducing complexity is the primary reason we make functions

First, let's derive our very own Y-combinator

// standard definition
const Y = f => f (Y (f))

// prevent immediate infinite recursion in applicative order language (JS)
const Y = f => f (x => Y (f) (x))

// remove reference to self using U combinator
const Y = U (h => f => f (x => U (h) (f) (x)))

Now we will see how it's usage compares to the U-combinator. Notice, to recur, instead of U (f) we can simply call f ()

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

Y (f => (console.log ('stack overflow imminent!'),  f ()))

Now I'll demonstrate the countDown program using Y – you'll see the programs are almost identical but the Y combinator keeps things a bit cleaner

const log = x => (console.log (x), x)

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const countDown = Y (f => x => x > 0 ? f (log (x - 1)) : 0)

countDown (5)
// 4 3 2 1 0

countDown (3)
// 2 1 0

And now we'll see factorial as well

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const factorial = Y (f => x =>
  x === 0 ? 1 :  x * f (x - 1))

console.log (factorial (5)) // 120

As you can see, f becomes the mechanism for recursion itself. To recur, we call it like an ordinary function. We can call it multiple times with different arguments and the result will still be correct. And since it's an ordinary function parameter, we can name it whatever we like, such as recur below -

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const fibonacci = Y (recur => n =>
  n < 2 ? n : recur (n - 1) +  (n - 2))

console.log (fibonacci (10)) // 55

---

U and Y combinator with more than 1 parameter

In the examples above, we saw how we can loop and pass an argument to keep track of the "state" of our computation. But what if we need to keep track of additional state?

We could use compound data like an Array or something...

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const fibonacci = Y (f => ([a, b, x]) =>
  x === 0 ? a : f ([b, a + b, x - 1]))

// starting with 0 and 1, generate the 7th number in the sequence
console.log (fibonacci ([0, 1, 7])) 
// 0 1 1 2 3 5 8 13

But this is bad because it's exposing internal state (counters a and b). It would be nice if we could just call fibonacci (7) to get the answer we want.

Using what we know about curried functions (sequences of unary (1-paramter) functions), we can achieve our goal easily without having to modify our definition of Y or rely upon compound data or advanced language features.

Look at the definition of fibonacci closely below. We're immediately applying 0 and 1 which are bound to a and b respectively. Now fibonacci is simply waiting for the last argument to be supplied which will be bound to x. When we recurse, we must call f (a) (b) (x) (not f (a,b,x)) because our function is in curried form.

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const fibonacci = Y (f => a => b => x =>
  x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)

console.log (fibonacci (7)) 
// 0 1 1 2 3 5 8 13

---

This sort of pattern can be useful for defining all sorts of functions. Below we'll see two more functions defined using the Y combinator (range and reduce) and a derivative of reduce, map.

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const range = Y (f => acc => min => max =>
  min > max ? acc : f ([...acc, min]) (min + 1) (max)) ([])

const reduce = Y (f => g => y => ([x,...xs]) =>
  x === undefined ? y : f (g) (g (y) (x)) (xs))
  
const map = f =>
  reduce (ys => x => [...ys, f (x)]) ([])
  
const add = x => y => x + y

const sq = x => x * x

console.log (range (-2) (2))
// [ -2, -1, 0, 1, 2 ]

console.log (reduce (add) (0) ([1,2,3,4]))
// 10

console.log (map (sq) ([1,2,3,4]))
// [ 1, 4, 9, 16 ]

---

IT'S ALL ANONYMOUS OMG

Because we're working with pure functions here, we can substitute any named function for its definition. Watch what happens when we take fibonacci and replace named functions with their expressions

/* const U = f => f (f)
 *
 * const Y = U (h => f => f (x => U (h) (f) (x)))
 *
 * const fibonacci = Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
 *
 */

/*
 * given fibonacci (7)
 *
 * replace fibonacci with its definition
 * Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
 *
 * replace Y with its definition
 * U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
//
 * replace U with its definition
 * (f => f (f)) U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
 */

let result =
  (f => f (f)) (h => f => f (x => h (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
  
console.log (result) // 13

And there you have it – fibonacci (7) calculated recursively using nothing but anonymous functions

Kapoor

oh my god, that a lot of haskell inside javascript – Cockney

Answer 3

People talked about the Y combinator in comments, but no one wrote it as an answer.

The Y combinator can be defined in javascript as follows: (thanks to steamer25 for the link)

var Y = function (gen) {
  return (function(f) {
    return f(f);
  }(function(f) {
    return gen(function() {
      return f(f).apply(null, arguments);
    });
  }));
}

And when you want to pass your anonymous function:

(Y(function(recur) {
  return function(data) {
    data = data+1;
    var nothing = function() {
      recur(data);
    }
    nothing();
  }
})());

The most important thing to note about this solution is that you shouldn't use it.

Apteryx

"The most important thing to note about this solution is that you shouldn't use it." Why? – Bistort

It will not be fast. It's ugly to actually use (though conceptually beautiful!). You avoid having to give your function a tag or variable name (and I don't see why that would be a concern), but you still give it a name as the parameter to the outer function passed to Y. So you don't gain anything by going through all this trouble. – Apteryx

Don't forget to mention this function isn't stack safe. Looping just a couple thousand times will result in a stack overflow. – Kapoor

Hi, I would propose slightly "cleaner" modification since .apply(null,arguments) seems ugly to me: var Y = function (gen) { return (function(f) { return f(f); }(function(f) { return gen(function(x) { return f(f)(x); }); })); } Or equivalently (( function(x){return y} equals (x => y) )) by using arrow notation (valid js code): var Y = gen => ( f => f(f) ) ( f => gen ( x => f(f)(x) ) ) – Athamas

Answer 4

It may be simplest to use an "anonymous object" instead:

({
  do: function() {
    console.log("don't run this ...");
    this.do();
  }
}).do();

Your global space is completely unpolluted. It's pretty straightforward. And you can easily take advantage of the object's non-global state.

You can also use ES6 object methods to make the syntax more concise.

({
  do() {
    console.log("don't run this ...");
    this.do();
  }
}).do();

Appendicitis

Note: This doesn't with Array.map or Array.forEach. Alternative: We don't want to pollute the global scope and this is easily achievable with the use of modules. If you divide your code into modules, the function won't pollute the global scope. It will stay unexported and only "pollute" the space of its module. Yeah we sacrifices readability, but hey, it works at least. – Embodiment

Answer 5

I would not do this as an inline function. It's pushing against the boundaries of good taste and doesn't really get you anything.

If you really must, there is arguments.callee as in Fabrizio's answer. However this is generally considered inadvisable and is disallowed in ECMAScript Fifth Edition's ‘strict mode’. Although ECMA 3 and non-strict-mode are not going away, working in strict mode promises more possible language optimisations.

One can also use a named inline function:

(function foo(data){
    data++;
    var nothing = function() {
        foo(data);
    }
    nothing();
})();

However named inline function expressions are also best avoided, as IE's JScript does some bad things to them. In the above example foo incorrectly pollutes the parent scope in IE, and the parent foo is a separate instance to the foo seen inside foo.

What's the purpose of putting this in an inline anonymous function? If you just want to avoid polluting the parent scope, you can of course hide your first example inside another self-calling-anonymous-function (namespace). Do you really need to create a new copy of nothing each time around the recursion? You might be better off with a namespace containing two simple mutually-recursive functions.

Heigho

I agree, a named function is more suitable than arguments.callee not only for the ecmascript strict mode, but also for a matter of optimization because at each recursion he need to get a reference to the callee (and this probably could reduce the execution speed) – Titter

+1 for the poetic, "pushing against the boundaries of good taste" - (well, and the good info). – Junina

what about a simple pre/postfix if pollution is really a concern here? Considering that it's not in the global scope (even if the function is top lvl, he should already have an anonymous function wrapping his whole code) it's really unlikely that a name like recur_foo will collide with a function in the parent scope (or to be ill-used) . – Swetlana

Very interesting - jsfiddle.net/hck2A - IE does pollute the parent in this case, like you said. Never realized that. – Junina

@Peter: kangax.github.com/nfe (especially ‘JScript bugs’) for more than you ever wanted to know on this subject. It's finally fixed in IE9 (but only in IE9 Standards Mode). – Heigho

Answer 6

(function(data){
    var recursive = arguments.callee;
    data = data+1;
    var nothing = function() {
        recursive(data)
    }
    nothing();
})();

Titter

I hope everybody voting for this (technically correct) answer realizes the problems with arguments.callee: it's disallowed in strict mode and in ES5. – Stoichiometric

Voted down, arguments.callee is deprecated in ES5 – Risteau

It works in NodeJS. I couldn't care less about ES5 as long as it works in a predictable fashion on a fixed environment. – Linneman

This is a time bomb. There is no such thing called a "fixed" environment, as the comment above suggest. You would almost always upgrade because of any of the thousands of reasons to do so. – Caroylncarp

Answer 7

You could do something like:

(foo = function() { foo(); })()

or in your case:

(recur = function(data){
    data = data+1;
    var nothing = function() {
        if (data > 100) return; // put recursion limit
        recur(data);
    }
    nothing();
})(/* put data init value here */ 0);

Clover

You could do with declaring recur first with a var statement. Dunno whether that breaks the rules of the question, but as you have it now, without the var statement you'll get an error in ECMAScript 5 strict mode. – Lyndell

My initial comment included the var keyword, but once I tested this code, it was throwing errors, since you cannot really declare a variable inside of a self-invoking block, and my approach relies on auto declaration of an undefined variable, and therefore @Pointy's solution is more correct. But I still voted for Fabrizio Calderan answer though ;) – Clover

Yes, doing (var recur = function() {...})(); won't work since it's now a statement rather than an assignment expression (which returns the value assigned). I was suggesting var recur; (recur = function() {...})(); instead. – Lyndell

Answer 8

When you declare an anonymous function like this:

(function () {
    // Pass
}());

Its considered a function expression and it has an optional name (that you can use to call it from within itself. But because it's a function expression (and not a statement) it stays anonymous (but has a name that you can call). So this function can call itself:

(function foo () {
    foo();
}());
foo //-> undefined

Tehuantepec

"it stays anonymous" – no it doesn't. An anonymous function does not have a name. I understand that foo doesn't get declared within the current context, but that's more or less irrelevant. A function with a name is still a named function – not anonymous. – Kapoor

Answer 9

Why not pass the function to the functio itself ?

    var functionCaller = function(thisCaller, data) {
        data = data + 1;
        var nothing = function() {
            thisCaller(thisCaller, data);
        };
        nothing();
    };
    functionCaller(functionCaller, data);

Mukerji

Answer 10

In certain situations you have to rely on anonymous functions. Given is a recursive map function:

const map = f => acc => ([head, ...tail]) => head === undefined 
 ? acc
 : map (f) ([...acc, f(head)]) (tail);

const sqr = x => x * x;
const xs = [1,2,3,4,5];

console.log(map(sqr) ([0]) (xs)); // [0] modifies the structure of the array

Please note that map must not modify the structure of the array. So the accumulator acc needn't to be exposed. We can wrap map into another function for instance:

const map = f => xs => {
  let next = acc => ([head, ...tail]) => head === undefined
   ? acc
   : map ([...acc, f(head)]) (tail);

  return next([])(xs);
}

But this solution is quite verbose. Let's use the underestimated U combinator:

const U = f => f(f);

const map = f => U(h => acc => ([head, ...tail]) => head === undefined 
 ? acc
 : h(h)([...acc, f(head)])(tail))([]);

const sqr = x => x * x;
const xs = [1,2,3,4,5];

console.log(map(sqr) (xs));

Concise, isn't it? U is dead simple but has the disadvantage that the recursive call gets a bit obfuscated: sum(...) becomes h(h)(...) - that's all.

Hatred

Answer 11

I am not sure if the answer is still required but this can also be done using delegates created using function.bind:

    var x = ((function () {
        return this.bind(this, arguments[0])();
    }).bind(function (n) {
        if (n != 1) {
            return n * this.bind(this, (n - 1))();
        }
        else {
            return 1;
        }
    }))(5);

    console.log(x);

This does not involve named functions or arguments.callee.

Phagocytosis

Answer 12

With ES2015 we can play around a bit with the syntax and abuse default parameters and thunks. The latter are just functions without any arguments:

const applyT = thunk => thunk();

const fib = n => applyT(
  (f = (x, y, n) => n === 0 ? x : f(y, x + y, n - 1)) => f(0, 1, n)
);

console.log(fib(10)); // 55

// Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

Please note that f is a parameter with the anonymous function (x, y, n) => n === 0 ? x : f(y, x + y, n - 1) as its default value. When f is invoked by applyT this invocation must take place without arguments, so that the default value is used. The default value is a function and hence f is a named function, which can call itself recursively.

Hatred

Answer 13

Like bobince wrote, simply name your function.

But, I'm guessing you also want to pass in an initial value and stop your function eventually!

var initialValue = ...

(function recurse(data){
    data++;
    var nothing = function() {
        recurse(data);
    }
    if ( ... stop condition ... )
        { ... display result, etc. ... }
    else
        nothing();
}(initialValue));

working jsFiddle example (uses data += data for fun)

Junina

+1, This is a very useful answer and you should get more upvotes for it, but it's not anonymous. – Splenectomy

you clearly didn't read what bobince wrote: However named inline function expressions are also best avoided.. But the OP misses the point too... :) – Swetlana

@Galamb - I read it. Disallowed in strict mode and in ES5 is not the same as polluting a parent scope and creating extra instances. – Junina

Answer 14

i needed (or rather, wanted) an one-liner anonymous function to walk its way up an object building up a string, and handled it like this:

var cmTitle = 'Root' + (function cmCatRecurse(cmCat){return (cmCat == root) ? '' : cmCatRecurse(cmCat.parent) + ' : ' + cmCat.getDisplayName();})(cmCurrentCat);

which produces a string like 'Root : foo : bar : baz : ...'

Seljuk

Answer 15

Another answer which does not involve named function or arguments.callee

var sum = (function(foo,n){
  return n + foo(foo,n-1);
})(function(foo,n){
     if(n>1){
         return n + foo(foo,n-1)
     }else{
         return n;
     }
},5); //function takes two argument one is function and another is 5

console.log(sum) //output : 15

Whomsoever

nice: bind an anonymous function to a local parameter and then call the function via the local parameter, but also pass the function to itself for the recursion. – Sandberg

Answer 16

This is a rework of jforjs answer with different names and a slightly modified entry.

// function takes two argument: first is recursive function and second is input
var sum = (function(capturedRecurser,n){
  return capturedRecurser(capturedRecurser, n);
})(function(thisFunction,n){
     if(n>1){
         return n + thisFunction(thisFunction,n-1)
     }else{
         return n;
     }
},5); 

console.log(sum) //output : 15

There was no need to unroll the first recursion. The function receiving itself as a reference harkens back to the primordial ooze of OOP.

Sandberg

Answer 17

This is a version of @zem's answer with arrow functions.

You can use the U or the Y combinator. Y combinator being the simplest to use.

U combinator, with this you have to keep passing the function: const U = f => f(f) U(selfFn => arg => selfFn(selfFn)('to infinity and beyond'))

Y combinator, with this you don't have to keep passing the function: const Y = gen => U(f => gen((...args) => f(f)(...args))) Y(selfFn => arg => selfFn('to infinity and beyond'))

Proverb

Answer 18

This may not work everywhere, but you can use arguments.callee to refer to the current function.

So, factorial could be done thus:

var fac = function(x) { 
    if (x == 1) return x;
    else return x * arguments.callee(x-1);
}

Mozell

Answer 19

Yet another Y-combinator solution, using rosetta-code link (I think somebody previously mentioned the link somewhere on stackOverflow.

Arrows are for anonymous functions more readable to me:

var Y = f => (x => x(x))(y => f(x => y(y)(x)));

Athamas

Answer 20

I don't suggest doing this in any practical use-case, but just as a fun exercise, you can actually do this using a second anonymous function!

(f => f(f))(f => {
    data = data+1;
    var nothing = function() {
        f();
    }
    nothing(f);
});

The way this works is that we're passing the anonymous function as an argument to itself, so we can call it from itself.

Lemar

Answer 21

by using arguments.callee(). For more details visit this url: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions#scope_and_the_function_stack

(function(data){
    data = data+1;
    var nothing = function() {
       arguments.callee() // this calls the function itself
    }
    nothing();
})();

Ugrian

This is deprecated function and will cause error because it will be removed in the future. Reference : link. For an old browser, okay. For current and future, NO – Vallecula