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.

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.

Answer 2

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.

Answer 3

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

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();

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.

Answer 6

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

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);

Answer 8

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);

Answer 9

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.

Answer 10

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

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.

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.

Answer 13

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 : ...'

Answer 14

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)

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

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.

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'))

Answer 18

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)));

Answer 19

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.

Answer 20

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();
})();

Answer 21

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);
}