How do I write an arrow function in ES6 recursivel

问题:

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?

回答1:

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.

回答2:

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

回答3:

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

回答4:

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

回答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

回答6:

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?

回答7:

var rec = () => {rec()};
rec();

Would that be an option?

回答8:

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

回答9:

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

回答10:

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