Calling a javascript function recursively

Question

I can create a recursive function in a variable like so:

/* Count down to 0 recursively.
 */
var functionHolder = function (counter) {
    output(counter);
    if (counter > 0) {
        functionHolder(counter-1);
    }
}

With this, functionHolder(3); would output 3 2 1 0. Let's say I did the following:

var copyFunction = functionHolder;

copyFunction(3); would output 3 2 1 0 as above. If I then changed functionHolder as follows:

functionHolder = function(whatever) {
    output("Stop counting!");

Then functionHolder(3); would give Stop counting!, as expected.

copyFunction(3); now gives 3 Stop counting! as it refers to functionHolder, not the function (which it itself points to). This could be desirable in some circumstances, but is there a way to write the function so that it calls itself rather than the variable that holds it?

That is, is it possible to change only the line functionHolder(counter-1); so that going through all these steps still gives 3 2 1 0 when we call copyFunction(3);? I tried this(counter-1); but that gives me the error this is not a function.

Solution 1

Using Named Function Expressions:

You can give a function expression a name that is actually private and is only visible from inside of the function ifself:

var factorial = function myself (n) {
    if (n <= 1) {
        return 1;
    }
    return n * myself(n-1);
}
typeof myself === 'undefined'

Here myself is visible only inside of the function itself.

You can use this private name to call the function recursively.

See 13. Function Definition of the ECMAScript 5 spec:

The Identifier in a FunctionExpression can be referenced from inside the FunctionExpression's FunctionBody to allow the function to call itself recursively. However, unlike in a FunctionDeclaration, the Identifier in a FunctionExpression cannot be referenced from and does not affect the scope enclosing the FunctionExpression.

Please note that Internet Explorer up to version 8 doesn't behave correctly as the name is actually visible in the enclosing variable environment, and it references a duplicate of the actual function (see patrick dw's comment below).

Using arguments.callee:

Alternatively you could use arguments.callee to refer to the current function:

var factorial = function (n) {
    if (n <= 1) {
        return 1;
    }
    return n * arguments.callee(n-1);
}

The 5th edition of ECMAScript forbids use of arguments.callee() in strict mode, however:

(From MDN): In normal code arguments.callee refers to the enclosing function. This use case is weak: simply name the enclosing function! Moreover, arguments.callee substantially hinders optimizations like inlining functions, because it must be made possible to provide a reference to the un-inlined function if arguments.callee is accessed. arguments.callee for strict mode functions is a non-deletable property which throws when set or retrieved.

Solution 2

You can access the function itself using arguments.callee ^[MDN]:

if (counter>0) {
    arguments.callee(counter-1);
}

This will break in strict mode, however.

Solution 3

You can use the Y-combinator: (Wikipedia)

// ES5 syntax
var Y = function Y(a) {
  return (function (a) {
    return a(a);
  })(function (b) {
    return a(function (a) {
      return b(b)(a);
    });
  });
};

// ES6 syntax
const Y = a=>(a=>a(a))(b=>a(a=>b(b)(a)));

// If the function accepts more than one parameter:
const Y = a=>(a=>a(a))(b=>a((...a)=>b(b)(...a)));

And you can use it as this:

// ES5
var fn = Y(function(fn) {
  return function(counter) {
    console.log(counter);
    if (counter > 0) {
      fn(counter - 1);
    }
  }
});

// ES6
const fn = Y(fn => counter => {
  console.log(counter);
  if (counter > 0) {
    fn(counter - 1);
  }
});

Solution 4

I know this is an old question, but I thought I'd present one more solution that could be used if you'd like to avoid using named function expressions. (Not saying you should or should not avoid them, just presenting another solution)

  var fn = (function() {
    var innerFn = function(counter) {
      console.log(counter);

      if(counter > 0) {
        innerFn(counter-1);
      }
    };

    return innerFn;
  })();

  console.log("running fn");
  fn(3);

  var copyFn = fn;

  console.log("running copyFn");
  copyFn(3);

  fn = function() { console.log("done"); };

  console.log("fn after reassignment");
  fn(3);

  console.log("copyFn after reassignment of fn");
  copyFn(3);

Solution 5

Here's one very simple example:

var counter = 0;

function getSlug(tokens) {
    var slug = '';

    if (!!tokens.length) {
        slug = tokens.shift();
        slug = slug.toLowerCase();
        slug += getSlug(tokens);

        counter += 1;
        console.log('THE SLUG ELEMENT IS: %s, counter is: %s', slug, counter);
    }

    return slug;
}

var mySlug = getSlug(['This', 'Is', 'My', 'Slug']);
console.log('THE SLUG IS: %s', mySlug);

Notice that the counter counts "backwards" in regards to what slug's value is. This is because of the position at which we are logging these values, as the function recurs before logging -- so, we essentially keep nesting deeper and deeper into the call-stack before logging takes place.

Once the recursion meets the final call-stack item, it trampolines "out" of the function calls, whereas, the first increment of counter occurs inside of the last nested call.

I know this is not a "fix" on the Questioner's code, but given the title I thought I'd generically exemplify Recursion for a better understanding of recursion, outright.

View more solutions

Comments

[Arnaud Le Blanc]

I believe that this is deprecated (and not allowed in strict mode)

[user113716]

+1 Although it's a little buggy in IE8 and lower in that myself is actually visible in the enclosing variable environment, and it references a duplicate of the actual myself function. You should be able to set the outer reference to null though.

[user113716]

@Felix: Yeah, "strict mode" will give a TypeError, but I haven't found anything that officially states that arguments.callee (or any strict mode violation) is deprecated outside of "strict mode".

[Samthere]

Thanks for the answer! Both were helpful and solved the problem, in 2 different ways. In the end I randomly decided which to accept :P

[Samthere]

Thanks for the answer! Both were helpful and solved the problem, in 2 different ways. In the end I randomly decided which to accept :P

[chitzui]

just for me to understand. What is the reason behind multiplying the function on each return? return n * myself(n-1); ?

[Prashant Tapase]

why function works like this? jsfiddle.net/jvL5euho/18 after if looping 4 times.

[Krunal Limbad]

As per some reference arguments.callee will not work in strict mode.