50

Arrow functions in ES6 do not have an arguments property and therefore arguments.callee will not work and would anyway not work in strict mode even if just an anonymous function was being used.

Arrow functions cannot be named, so the named functional expression trick can not be used.

So... How does one write a recursive arrow function? That is an arrow function that recursively calls itself based on certain conditions and so on of-course?

5
  • 3
    You can use usual functions, probably arrow functions is not a right tool for recursion calls.
    – dfsq
    Aug 10, 2014 at 12:06
  • A factorial function is one statement if the ternary operator is used. A single statement anonymous function is certainly a use case for an arrow function.
    – Siddharth
    Aug 10, 2014 at 12:08
  • 1
    Why not assigning the function to a variable, which in turn is in scope of the function body?
    – philipp
    Aug 10, 2014 at 12:16
  • That wouldn't be very robust. If the function is assigned to a different variable and the original is reassigned to a new value, your code breaks. This can be solved using a named functional expression usually, but arrow functions cannot be named, not in their own scope at least.
    – Siddharth
    Aug 10, 2014 at 12:21
  • If you use const, then the original can't be re-assigned. Seems perfectly robust, and indeed, is now widely used.
    – Dtipson
    Feb 9, 2016 at 1:35

13 Answers 13

41

Writing a recursive function without naming it is a problem that is as old as computer science itself (even older, actually, since λ-calculus predates computer science), since in λ-calculus all functions are anonymous, and yet you still need recursion.

The solution is to use a fixpoint combinator, usually the Y combinator. This looks something like this:

(y => 
  y(
    givenFact => 
      n => 
        n < 2 ? 1 : n * givenFact(n-1)
  )(5)
)(le => 
  (f => 
    f(f)
  )(f => 
    le(x => (f(f))(x))
  )
);

This will compute the factorial of 5 recursively.

Note: the code is heavily based on this: The Y Combinator explained with JavaScript. All credit should go to the original author. I mostly just "harmonized" (is that what you call refactoring old code with new features from ES/Harmony?) it.

11
  • 32
    Seriously... if someone actually uses a Y combinator instead of naming a function... (nice answer to a question with a terrible premise ;-) ) Aug 11, 2014 at 6:00
  • 3
    @impinball: That answer assigns the function to a variable, which the OP disallowed. I know that's stupid, you know that's stupid, everybody knows that's stupid, but that's what the requirements are. Aug 29, 2014 at 8:11
  • 1
    I like "harmonize" better than "harmonicalize" for the same reasons that I like "canonize" better than "canonicalize". Jun 13, 2016 at 19:11
  • 2
    That looks terrifying.
    – sdfsdf
    Jul 29, 2016 at 17:36
  • 1
    The answer is interesting but the code it self could make your teammate really confused. Naming it would be a better workaround.
    – yuan
    Mar 26, 2019 at 7:35
23

It looks like you can assign arrow functions to a variable and use it to call the function recursively.

var complex = (a, b) => {
    if (a > b) {
        return a;
    } else {
        complex(a, b);
    }
};
6
  • 1
    complex(2,3) gives InternalError: too much recursion Aug 10, 2014 at 12:18
  • 1
    Yeah, its just a simple function to show recursive calls.
    – user405398
    Aug 10, 2014 at 12:19
  • 1
    This couples the function to the name. Bad idea.
    – Siddharth
    Aug 10, 2014 at 12:23
  • 7
    @OrtomalaLokni why does he have to make it a working factorial function? Aug 10, 2014 at 12:26
  • 13
    Thats ridiculous. Any example of a recursive function is a valid answer to the question. The asker doesnt like assigning the function to a name, and for that reason probably wont accept this answer, but your complaint against TamilVendhan is absurd... Aug 10, 2014 at 12:32
17

Claus Reinke has given an answer to your question in a discussion on the esdiscuss.org website.

In ES6 you have to define what he calls a recursion combinator.

 let rec = (f)=> (..args)=> f( (..args)=>rec(f)(..args), ..args )

If you want to call a recursive arrow function, you have to call the recursion combinator with the arrow function as parameter, the first parameter of the arrow function is a recursive function and the rest are the parameters. The name of the recursive function has no importance as it would not be used outside the recursive combinator. You can then call the anonymous arrow function. Here we compute the factorial of 6.

 rec( (f,n) => (n>1 ? n*f(n-1) : n) )(6)

If you want to test it in Firefox you need to use the ES5 translation of the recursion combinator:

function rec(f){ 
    return function(){
        return f.apply(this,[
                               function(){
                                  return rec(f).apply(this,arguments);
                                }
                            ].concat(Array.prototype.slice.call(arguments))
                      );
    }
}
1
  • Just want to clear (.. vs ...): let rec = (f)=> (...args)=> f( (...args)=>rec(f)(...args), ...args ); rec( (f,n) => (n>1 ? n*f(n-1) : n) )(6);
    – aviit
    Sep 6, 2018 at 6:11
11

TL;DR:

const rec = f => f((...xs) => rec(f)(...xs));

There are many answers here with variations on a proper Y -- but that's a bit redundant... The thing is that the usual way Y is explained is "what if there is no recursion", so Y itself cannot refer to itself. But since the goal here is a practical combinator, there's no reason to do that. There's this answer that defines rec using itself, but it's complicated and kind of ugly since it adds an argument instead of currying.

The simple recursively-defined Y is

const rec = f => f(rec(f));

but since JS isn't lazy, the above adds the necessary wrapping.

1
  • 2
    This is the real answer here. No need to jump straight to a full y-combinator implementation as we aren't in a language without recursion.
    – slazarus
    Feb 25, 2020 at 23:38
10

Use a variable to which you assign the function, e.g.

const fac = (n) => n>0 ? n*fac(n-1) : 1;

If you really need it anonymous, use the Y combinator, like this:

const Y = (f) => ((x)=>f((v)=>x(x)(v)))((x)=>f((v)=>x(x)(v)))
… Y((fac)=>(n)=> n>0 ? n*fac(n-1) : 1) …

(ugly, isn't it?)

1
  • 5
    Very ugly, but conceptually so beautiful.
    – Siddharth
    Aug 10, 2014 at 22:53
6

I found the provided solutions really complicated, and honestly couldn't understand any of them, so i thought out a simpler solution myself (I'm sure it's already known, but here goes my thinking process):

So you're making a factorial function

x => x < 2 ? x : x * (???)

the (???) is where the function is supposed to call itself, but since you can't name it, the obvious solution is to pass it as an argument to itself

f => x => x < 2 ? x : x * f(x-1)

This won't work though. because when we call f(x-1) we're calling this function itself, and we just defined it's arguments as 1) f: the function itself, again and 2) x the value. Well we do have the function itself, f remember? so just pass it first:

f => x => x < 2 ? x : x * f(f)(x-1)
                            ^ the new bit

And that's it. We just made a function that takes itself as the first argument, producing the Factorial function! Just literally pass it to itself:

(f => x => x < 2 ? x : x * f(f)(x-1))(f => x => x < 2 ? x : x * f(f)(x-1))(5)
>120

Instead of writing it twice, you can make another function that passes it's argument to itself:

y => y(y)

and pass your factorial making function to it:

(y => y(y))(f => x => x < 2 ? x : x * f(f)(x-1))(5)
>120

Boom. Here's a little formula:

(y => y(y))(f => x => endCondition(x) ? default(x) : operation(x)(f(f)(nextStep(x))))

For a basic function that adds numbers from 0 to x, endCondition is when you need to stop recurring, so x => x == 0. default is the last value you give once endCondition is met, so x => x. operation is simply the operation you're doing on every recursion, like multiplying in Factorial or adding in Fibonacci: x1 => x2 => x1 + x2. and lastly nextStep is the next value to pass to the function, which is usually the current value minus one: x => x - 1. Apply:

(y => y(y))(f => x => x == 0 ? x : x + f(f)(x - 1))(5)
>15
2
  • 1
    This is called the U combinator const U = f => f(f)
    – user6445533
    Nov 17, 2017 at 14:41
  • 1
    This one is way more readable.
    – khaiyom
    May 14 at 1:50
5

A general purpose combinator for recursive function definitions of any number of arguments (without using the variable inside itself) would be:

const rec = (le => ((f => f(f))(f => (le((...x) => f(f)(...x))))));

This could be used for example to define factorial:

const factorial = rec( fact => (n => n < 2 ? 1 : n * fact(n - 1)) );
//factorial(5): 120

or string reverse:

const reverse = rec(
  rev => (
    (w, start) => typeof(start) === "string" 
                ? (!w ? start : rev(w.substring(1), w[0] + start)) 
                : rev(w, '')
  )
);
//reverse("olleh"): "hello"

or in-order tree traversal:

const inorder = rec(go => ((node, visit) => !!(node && [go(node.left, visit), visit(node), go(node.right, visit)])));

//inorder({left:{value:3},value:4,right:{value:5}}, function(n) {console.log(n.value)})
// calls console.log(3)
// calls console.log(4)
// calls console.log(5)
// returns true
3
var rec = () => {rec()};
rec();

Would that be an option?

4
  • Please read my last comment on the question. This is coupled strongly to the variable it is assigned to. Reassign it to another and reassign rec to anything else and it breaks.
    – Siddharth
    Aug 10, 2014 at 12:26
  • 1
    Well , I guess arrow functions cannot do what you desire, so you need to use a regular one.
    – philipp
    Aug 10, 2014 at 12:30
  • Wrap it in a closure.
    – sleblanc
    Aug 10, 2014 at 15:44
  • But that would require to write function as well and does not shorten the required code, too. Of course can one go in circles where a straight line is possible, but if it makes sense is another question.
    – philipp
    Aug 10, 2014 at 16:47
3

Since arguments.callee is a bad option due to deprecation/doesnt work in strict mode, and doing something like var func = () => {} is also bad, this a hack like described in this answer is probably your only option:

javascript: recursive anonymous function?

6
  • The property is deprecated and is not recommended for use. Also won't work in strict mode.
    – Siddharth
    Aug 10, 2014 at 12:13
  • 1
    And ES6 modules are implicitly strict without opt-out IIRC. Aug 10, 2014 at 12:14
  • Writing "use strict"; into my console and then re-running the code didnt throw any errors. EDIT: This comment is wrong, you are right. Aug 10, 2014 at 12:17
  • 1
    @Siddharth Seeing as arguments.callee is not allowed, and you dont want to do something like func = () => {}, there probably isnt any way, though you can use the hack like in the other SO answer that I linked to. Aug 10, 2014 at 12:24
  • "var func = () => {}" - wait, why? Aug 10, 2014 at 18:02
2

This is a version of this answer, https://stackoverflow.com/a/3903334/689223, 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'))

0

You can assign your function to a variable inside an iife

var countdown = f=>(f=a=>{
  console.log(a)
  if(a>0) f(--a)
})()

countdown(3)

//3
//2
//1
//0
0

i think the simplest solution is looking at the only thing that you don't have, which is a reference to the function itself. because if you have that then recusion is trivial.

amazingly that is possible through a higher order function.

let generateTheNeededValue = (f, ...args) => f(f, ...args);

this function as the name sugests, it will generate the reference that we'll need. now we only need to apply this to our function

(generateTheNeededValue)(ourFunction, ourFunctionArgs)

but the problem with using this thing is that our function definition needs to expect a very special first argument

let ourFunction = (me, ...ourArgs) => {...}

i like to call this special value as 'me'. and now everytime we need recursion we do like this

me(me, ...argsOnRecursion);

with all of that. we can now create a simple factorial function.

((f, ...args) => f(f, ...args))((me, x) => {
  if(x < 2) {
    return 1;
  } else {
    return x * me(me, x - 1);
  }
}, 4)

-> 24

i also like to look at the one liner of this

((f, ...args) => f(f, ...args))((me, x) => (x < 2) ? 1 : (x * me(me, x - 1)), 4)
1
  • all of this will put more logic and considerations on your functions. so i don't recommend using it. it's much simpler to just have that reference and use that instead. there is no problem with that. you really will only use this if someone forces you because the tools and languages we have today will definitely allow us to have that value. May 24, 2019 at 23:28
0

Here is the example of recursive function js es6.

 let filterGroups = [
     {name: 'Filter Group 1'}
 ];


 const generateGroupName = (nextNumber) => {
    let gN = `Filter Group ${nextNumber}`;
    let exists = filterGroups.find((g) => g.name === gN);
    return exists === undefined ? gN : generateGroupName(++nextNumber); // Important
 };


 let fg = generateGroupName(filterGroups.length);
 filterGroups.push({name: fg});

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.