javascript: función anónima recursiva?

Digamos que tengo una función recursiva básica:

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

¿Cómo podría hacer esto si tengo una función anónima como ...

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

Me gustaría una forma de llamar a la función que llamó a esta función ... He visto scripts en alguna parte (no recuerdo dónde) que pueden indicarle el nombre de una función llamada, pero no recuerdo ninguno de esa información ahora mismo.

Usted puede dar a la función de un nombre, incluso cuando se va a crear la función como un valor y no una declaración "declaración de la función". En otras palabras:

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

es una función recursiva acumulativa. Ahora bien, dicho esto, probablemente no quieras hacer esto en general porque hay algunos problemas extraños con varias implementaciones de Javascript. ( nota : es un comentario bastante antiguo; algunos / muchos / todos los problemas descritos en la publicación del blog de Kangax pueden solucionarse en navegadores más modernos).

Cuando le da un nombre así, el nombre no es visible fuera de la función (bueno, no se supone que lo sea; esa es una de las rarezas). Es como "letrec" en Lisp.

En cuanto a arguments.callee, eso no está permitido en el modo "estricto" y generalmente se considera algo malo, porque dificulta algunas optimizaciones. También es mucho más lento de lo que cabría esperar.

editar : si desea tener el efecto de una función "anónima" que puede llamarse a sí misma, puede hacer algo como esto (asumiendo que está pasando la función como una devolución de llamada o algo así):

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

Lo que hace es definir una función con una declaración de declaración de función agradable, segura y no rota en IE , creando una función local cuyo nombre no contaminará el espacio de nombres global. La función contenedora (verdaderamente anónima) simplemente devuelve esa función local.

La gente habló sobre el combinador Y en los comentarios, pero nadie lo escribió como respuesta.

El combinador Y se puede definir en javascript de la siguiente manera: (gracias a steamer25 por el enlace)

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

Y cuando quieras pasar tu función anónima:

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

Lo más importante a tener en cuenta sobre esta solución es que no debe usarla.

Combinador U

Al pasar una función a sí misma como argumento, una función puede repetirse usando su parámetro en lugar de su nombre. Entonces la función dada aU debe tener al menos un parámetro que se unirá a la función (en sí).

En el siguiente ejemplo, no tenemos una condición de salida, por lo que solo realizaremos un bucle indefinido hasta que ocurra un desbordamiento de pila.

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

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

Podemos detener la recursividad infinita usando una variedad de técnicas. Aquí, escribiré nuestra función anónima para devolver otra función anónima que está esperando una entrada; en este caso, algún número. Cuando se proporciona un número, si es mayor que 0, continuaremos recurriendo, de lo contrario devolveremos 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

Lo que no es evidente de inmediato aquí es que nuestra función, cuando se aplica por primera vez a sí misma utilizando el Ucombinador, devuelve una función que espera la primera entrada. Si le damos un nombre a esto, podemos construir de manera efectiva funciones recursivas usando lambdas (funciones anónimas)

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

Solo que esto no es recursividad directa , una función que se llama a sí misma usando su propio nombre. Nuestra definición de countDownno hace referencia a sí misma dentro de su cuerpo y aún así la recursividad es posible

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

Cómo eliminar la autorreferencia de una función existente usando el combinador U

Aquí le mostraré cómo tomar una función recursiva que usa una referencia a sí misma y cambiarla a una función que emplea el combinador U en lugar de la autorreferencia.

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

Ahora usando el combinador U para reemplazar la referencia interna a factorial

const U = f => f (f)

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

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

El patrón de reemplazo básico es este. Tome nota mentalmente, usaremos una estrategia similar en la siguiente sección

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

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

Combinador Y

relacionado: los combinadores U e Y explicados usando una analogía de espejo

En la sección anterior vimos cómo transformar la recursividad de autorreferencia en una función recursiva que no depende de una función nombrada usando el combinador U. Hay un poco de molestia aunque tener que recordar pasar siempre la función a sí misma como primer argumento. Bueno, el combinador Y se basa en el combinador U y elimina esa parte tediosa. Esto es bueno porque eliminar / reducir la complejidad es la razón principal por la que hacemos funciones

Primero, derivemos nuestro propio combinador Y

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

Ahora veremos cómo se compara su uso con el combinador U. Observe, para recurrir, en lugar de U (f)simplemente podemos llamarf ()

const U = f => f (f)

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

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

Ahora demostraré el countDownuso del programa Y: verá que los programas son casi idénticos, pero el combinador Y mantiene las cosas un poco más limpias

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

Y ahora veremos factorialtambién

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

Como puede ver, se fconvierte en el propio mecanismo de recursividad. Para recurrir, lo llamamos como una función ordinaria. Podemos llamarlo varias veces con diferentes argumentos y el resultado seguirá siendo correcto. Y dado que es un parámetro de función ordinario, podemos nombrarlo como queramos, como a recurcontinuación:

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

Combinador U e Y con más de 1 parámetro

En los ejemplos anteriores, vimos cómo podemos hacer un bucle y pasar un argumento para realizar un seguimiento del "estado" de nuestro cálculo. Pero, ¿y si necesitamos realizar un seguimiento del estado adicional?

Nosotros podríamos utilizar los datos de compuestos como una matriz o algo ...

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

Pero esto es malo porque expone el estado interno (contadores ay b). Sería bueno si pudiéramos llamar fibonacci (7)para obtener la respuesta que queremos.

Usando lo que sabemos sobre funciones curry (secuencias de funciones unarias (1 parámetro)), podemos lograr nuestro objetivo fácilmente sin tener que modificar nuestra definición Yo depender de datos compuestos o características avanzadas del lenguaje.

Mira la definición de de fibonaccicerca a continuación. Estamos solicitando de inmediato 0y 1que están vinculados a ay brespectivamente. Ahora, fibonacci simplemente está esperando que se proporcione el último argumento al que se vinculará x. Cuando recurrimos, debemos llamar f (a) (b) (x)(no f (a,b,x)) porque nuestra función está en forma de curry.

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

Este tipo de patrón puede resultar útil para definir todo tipo de funciones. A continuación veremos dos funciones más definidas mediante el Ycombinador ( rangey reduce) y un derivado de 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 ]

TODO ES ANÓNIMO OMG

Como aquí estamos trabajando con funciones puras, podemos sustituir su definición por cualquier función nombrada. Observe lo que sucede cuando tomamos fibonacci y reemplazamos funciones nombradas con sus expresiones

/* 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

Y ahí lo tiene: fibonacci (7)calculado de forma recursiva utilizando nada más que funciones anónimas

Puede ser más sencillo utilizar un "objeto anónimo" en su lugar:

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

Su espacio global está completamente impoluto. Es bastante sencillo. Y puede aprovechar fácilmente el estado no global del objeto.

También puede utilizar métodos de objeto ES6 para hacer la sintaxis más concisa.

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

No haría esto como una función en línea. Es ir más allá de los límites del buen gusto y realmente no te ofrece nada.

Si realmente debe hacerlo, hay arguments.calleecomo en la respuesta de Fabrizio. Sin embargo, esto generalmente se considera desaconsejable y no está permitido en el 'modo estricto' de ECMAScript Quinta edición. Aunque ECMA 3 y el modo no estricto no desaparecerán, trabajar en modo estricto promete más optimizaciones de lenguaje posibles.

También se puede usar una función en línea con nombre:

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

Sin embargo, es mejor evitar las expresiones de función en línea con nombre, ya que JScript de IE les hace algunas cosas malas. En el ejemplo anterior foocontamina incorrectamente el alcance principal en IE, y el padre fooes una instancia separada del foovisto dentrofoo .

¿Cuál es el propósito de poner esto en una función anónima en línea? Si solo desea evitar contaminar el ámbito principal, por supuesto, puede ocultar su primer ejemplo dentro de otra función auto-llamada-anónima (espacio de nombres). ¿Realmente necesitas crear una nueva copia de nothingcada vez que se realiza la recursividad? Es posible que esté mejor con un espacio de nombres que contenga dos funciones recursivas recursivas simples.

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

Podrías hacer algo como:

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

o en tu caso:

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

Cuando declaras una función anónima como esta:

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

Se considera una expresión de función y tiene un nombre opcional (que puede usar para llamarla desde dentro de sí misma. Pero debido a que es una expresión de función (y no una declaración) permanece anónima (pero tiene un nombre que puede llamar). esta función puede llamarse a sí misma:

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

¿Por qué no pasar la función a la propia función?

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

En determinadas situaciones, debe confiar en funciones anónimas. Dado es una mapfunción recursiva :

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

Tenga en cuenta que mapno debe modificar la estructura de la matriz. Por tanto, accno es necesario exponer el acumulador . Podemos ajustarnos mapa otra función, por ejemplo:

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

  return next([])(xs);
}

Pero esta solución es bastante detallada. Usemos el Ucombinador subestimado :

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

Conciso, ¿no? Ues muy simple pero tiene la desventaja de que la llamada recursiva se ofusca un poco: se sum(...)convierte en h(h)(...)- eso es todo.

No estoy seguro de si aún se requiere la respuesta, pero esto también se puede hacer usando delegados creados usando 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);

Esto no implica funciones o argumentos con nombre.

Como escribió bobince, simplemente nombre su función.

Pero, supongo que también desea pasar un valor inicial y detener su función eventualmente.

var initialValue = ...

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

ejemplo de trabajo de jsFiddle (usa datos + = datos por diversión)

Necesitaba (o mejor dicho, quería) una función anónima de una sola línea para subir un objeto construyendo una cadena, y lo manejé así:

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

que produce una cadena como 'Root: foo: bar: baz: ...'

Con ES2015 podemos jugar un poco con la sintaxis y abusar de los parámetros y procesadores predeterminados. Estos últimos son solo funciones sin ningún argumento:

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

Tenga en cuenta que fes un parámetro con la función anónima (x, y, n) => n === 0 ? x : f(y, x + y, n - 1)como valor predeterminado. Cuando fes invocado por applyTesta invocación debe tener lugar sin argumentos, por lo que se utiliza el valor predeterminado. El valor predeterminado es una función y, por flo tanto, es una función con nombre, que puede llamarse a sí misma de forma recursiva.

Otra respuesta que no involucra una función o argumentos nombrados.

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

Esta es una reelaboración de la respuesta de jforjs con diferentes nombres y una entrada ligeramente modificada.

// 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

No fue necesario desenrollar la primera recursividad. La función que se recibe a sí misma como referencia se remonta al exudado primordial de la POO.

Esta es una versión de la respuesta de @ zem con funciones de flecha.

Puede utilizar el Uo elY combinador . El combinador Y es el más simple de usar.

U combinador, con esto tienes que seguir pasando la función: const U = f => f(f) U(selfFn => arg => selfFn(selfFn)('to infinity and beyond'))

Y combinador, con esto no tienes que seguir pasando la función: const Y = gen => U(f => gen((...args) => f(f)(...args))) Y(selfFn => arg => selfFn('to infinity and beyond'))

Otra solución de combinador en Y, usando el enlace de código rosetta (creo que alguien mencionó anteriormente el enlace en algún lugar de stackOverflow.

Las flechas son para funciones anónimas más legibles para mí:

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

Es posible que esto no funcione en todas partes, pero puede usarlo arguments.calleepara consultar la función actual.

Entonces, factorial podría hacerse así:

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