javascript: рекурсивная анонимная функция?

Скажем, у меня есть базовая рекурсивная функция:

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

Как я мог это сделать, если у меня есть анонимная функция, например ...

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

Мне нужен способ вызвать функцию, которая вызвала эту функцию ... Я где-то видел сценарии (не помню, где), которые могут сообщить вам имя вызываемой функции, но я не могу вспомнить ни одного из эта информация прямо сейчас.

Вы можете дать функции имя, даже если вы создаете функцию как значение, а не оператор «объявления функции». Другими словами:

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

является рекурсивной функцией сдува стека. С учетом сказанного, возможно , вы вообще не захотите этого делать, потому что существуют некоторые странные проблемы с различными реализациями Javascript. ( обратите внимание - это довольно старый комментарий; некоторые / многие / все проблемы, описанные в сообщении блога Kangax, могут быть исправлены в более современных браузерах.)

Когда вы даете такое имя, оно не отображается вне функции (ну, этого не должно быть; это одна из странностей). Это как "letrec" в Лиспе.

Что касается arguments.callee, это запрещено в «строгом» режиме и обычно считается плохим, потому что это затрудняет некоторые оптимизации. К тому же это намного медленнее, чем можно было ожидать.

edit - Если вы хотите получить эффект «анонимной» функции, которая может вызывать сама себя, вы можете сделать что-то вроде этого (при условии, что вы передаете функцию как обратный вызов или что-то в этом роде):

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

При этом определяется функция с красивым, безопасным, не нарушенным в IE оператором объявления функции , создавая локальную функцию, имя которой не будет загрязнять глобальное пространство имен. Функция-оболочка (действительно анонимная) просто возвращает эту локальную функцию.

Люди говорили о комбинаторе Y в комментариях, но никто не написал его в качестве ответа.

Комбинатор Y можно определить в javascript следующим образом: (спасибо steamer25 за ссылку)

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

И когда вы хотите передать свою анонимную функцию:

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

Самое важное, что следует отметить в этом решении, - это то, что вы не должны его использовать.

U комбинатор

Передавая функцию самой себе в качестве аргумента, функция может повторяться, используя свой параметр вместо имени! Таким образом, данная функция Uдолжна иметь хотя бы один параметр, который будет привязан к самой функции.

В приведенном ниже примере у нас нет условия выхода, поэтому мы будем просто бесконечно зацикливаться, пока не произойдет переполнение стека.

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

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

Мы можем остановить бесконечную рекурсию, используя различные методы. Здесь я напишу нашу анонимную функцию, чтобы возвращать другую анонимную функцию, ожидающую ввода; в данном случае какое-то количество. При вводе числа, если оно больше 0, мы продолжим повторение, иначе вернем 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

Что не сразу очевидно, так это то, что наша функция при первом применении к самой себе с помощью Uкомбинатора возвращает функцию, ожидающую первого ввода. Если бы мы дали этому имя, можно эффективно создавать рекурсивные функции, используя лямбды (анонимные функции).

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

Только это не прямая рекурсия - функция, которая вызывает себя по собственному имени. Наше определение countDownне ссылается на себя внутри своего тела, но рекурсия все же возможна.

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

Как удалить ссылку на себя из существующей функции с помощью U-комбинатора

Здесь я покажу вам, как взять рекурсивную функцию, которая использует ссылку на себя, и изменить ее на функцию, которая использует комбинатор U вместо ссылки на себя.

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

Теперь, используя комбинатор U для замены внутренней ссылки на factorial

const U = f => f (f)

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

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

Основная схема замены такова. Обратите внимание, мы будем использовать аналогичную стратегию в следующем разделе.

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

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

Y комбинатор

связанные: комбинаторы U и Y объяснены с использованием зеркальной аналогии

В предыдущем разделе мы увидели, как преобразовать рекурсию со ссылками на себя в рекурсивную функцию, которая не полагается на именованную функцию, используя U-комбинатор. Немного раздражает необходимость не забывать всегда передавать функцию самой себе в качестве первого аргумента. Что ж, Y-комбинатор основан на U-комбинаторе и устраняет этот утомительный элемент. Это хорошо, потому что устранение / уменьшение сложности - основная причина, по которой мы делаем функции.

Во-первых, давайте выведем наш собственный 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)))

Теперь посмотрим, как его использование сравнивается с U-комбинатором. Обратите внимание, чтобы повторить, вместо того, U (f)чтобы просто позвонить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 ()))

Теперь я продемонстрирую использование countDownпрограммы Y- вы увидите, что программы почти идентичны, но комбинатор Y делает вещи немного чище.

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

И теперь мы видим , factorialкак хорошо

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

Как видите, fсам механизм рекурсии становится. Повторюсь, мы называем это как обычную функцию. Мы можем вызывать его несколько раз с разными аргументами, и результат все равно будет правильным. А поскольку это обычный параметр функции, мы можем назвать его как угодно, например, recurниже -

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 и Y с более чем 1 параметром

В приведенных выше примерах мы увидели, как можно зацикливаться и передавать аргумент, чтобы отслеживать «состояние» наших вычислений. Но что, если нам нужно отслеживать дополнительное состояние?

Мы могли бы использовать составные данные, такие как массив или что-то в этом роде ...

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

Но это плохо, потому что выявляет внутреннее состояние (счетчики aи b). Было бы неплохо, если бы мы могли просто позвонить, fibonacci (7)чтобы получить нужный нам ответ.

Используя то, что мы знаем о каррированных функциях (последовательностях унарных (с одним параметром) функций), мы можем легко достичь нашей цели, не изменяя наше определение Y или полагаться на составные данные или расширенные языковые функции.

fibonacciВнимательно посмотрите на определение слова ниже. Сразу же подаем заявку 0и 1которые привязаны к aи bсоответственно. Теперь фибоначчи просто ждет, когда будет предоставлен последний аргумент, к которому будет привязан x. При рекурсии мы должны вызывать f (a) (b) (x)(не f (a,b,x)), потому что наша функция находится в каррированной форме.

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

Такой вид шаблона может быть полезен для определения всех видов функций. Ниже мы увидим еще две функции , определенные с помощью Yкомбинатора ( rangeа reduce) и производное 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 ]

ЭТО ВСЕ АНОНИМНОЕ OMG

Поскольку здесь мы работаем с чистыми функциями, мы можем заменить ее определение любой именованной функцией. Посмотрите, что происходит, когда мы берем фибоначчи и заменяем названные функции их выражениями

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

И вот оно - fibonacci (7)вычислено рекурсивно с использованием только анонимных функций.

Вместо этого может быть проще использовать «анонимный объект»:

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

Ваше глобальное пространство полностью незагрязнено. Это довольно просто. И вы можете легко воспользоваться неглобальным состоянием объекта.

Вы также можете использовать методы объекта ES6, чтобы сделать синтаксис более лаконичным.

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

Я бы не стал делать это как встроенную функцию. Это выходит за рамки хорошего вкуса и ничего вам не дает.

Если вам действительно нужно, есть arguments.calleeкак в ответе Фабрицио. Однако обычно это считается нецелесообразным и запрещено в «строгом режиме» ECMAScript Fifth Edition. Хотя ECMA 3 и нестрогий режим никуда не денутся, работа в строгом режиме обещает больше возможных оптимизаций языка.

Также можно использовать именованную встроенную функцию:

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

Однако лучше избегать именованных встроенных функциональных выражений, поскольку IE JScript делает с ними некоторые плохие вещи. В приведенном выше примере fooнеправильно загрязняет родительскую область видимости в IE, и родительский fooобъект является отдельным экземпляром для fooвидимого внутриfoo .

Какова цель использования встроенной анонимной функции? Если вы просто хотите избежать загрязнения родительской области видимости, вы, конечно, можете скрыть свой первый пример внутри другой самовызывающейся анонимной-функции (пространства имен). Вам действительно нужно создавать новую копию nothingкаждый раз вокруг рекурсии? Возможно, вам будет лучше использовать пространство имен, содержащее две простые взаимно рекурсивные функции.

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

Вы можете сделать что-то вроде:

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

или в вашем случае:

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

Когда вы объявляете анонимную функцию следующим образом:

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

Он считается функциональным выражением и имеет необязательное имя (которое вы можете использовать для вызова его изнутри самого себя. Но поскольку это выражение функции (а не оператор), оно остается анонимным (но имеет имя, которое вы можете вызвать). эта функция может вызывать сама себя:

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

Почему бы не передать функцию самой функции?

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

В определенных ситуациях вам придется полагаться на анонимные функции. Дана рекурсивная mapфункция:

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

Обратите внимание, что mapнельзя изменять структуру массива. Так что аккумулятор accвыставлять не нужно. Мы можем, например, перейти mapк другой функции:

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

  return next([])(xs);
}

Но это решение довольно многословное. Воспользуемся заниженным Uкомбинатором:

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

Лаконично, не правда ли? Uчрезвычайно прост, но имеет тот недостаток, что рекурсивный вызов немного запутывается: sum(...)становится h(h)(...)- вот и все.

Я не уверен, что ответ по-прежнему требуется, но это также можно сделать с помощью делегатов, созданных с помощью 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);

Это не касается именованных функций или arguments.callee.

Как написал bobince, просто назовите свою функцию.

Но я предполагаю, что вы также хотите передать начальное значение и в конечном итоге остановить свою функцию!

var initialValue = ...

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

рабочий пример jsFiddle (использует данные + = данные для развлечения)

Мне нужна была (или, скорее, хотелось) однострочная анонимная функция, которая двигалась бы вверх по объекту, формируя строку, и обработал ее следующим образом:

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

что создает строку типа 'Root: foo: bar: baz: ...'

В ES2015 мы можем немного поиграть с синтаксисом и злоупотреблять параметрами и преобразователями по умолчанию. Последние - это просто функции без аргументов:

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

Обратите внимание, что fэто параметр с анонимной функцией в (x, y, n) => n === 0 ? x : f(y, x + y, n - 1)качестве значения по умолчанию. Когда fвызывается applyTэтим вызовом, должно происходить без аргументов, чтобы использовалось значение по умолчанию. Значение по умолчанию - это функция и, следовательно, fименованная функция, которая может вызывать себя рекурсивно.

Другой ответ, который не включает названную функцию или аргументы. 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

Это переработанный ответ jforjs с другими именами и немного измененной записью.

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

Первую рекурсию разворачивать не пришлось. Функция, принимающая себя в качестве ссылки, восходит к исконной массе ООП.

Это версия ответа @zem со стрелочными функциями.

Вы можете использовать комбинатор Uили Y. Y-комбинатор - самый простой в использовании.

U комбинатор, при этом вы должны продолжать передавать функцию: const U = f => f(f) U(selfFn => arg => selfFn(selfFn)('to infinity and beyond'))

Y комбинатор, при этом вам не нужно постоянно передавать функцию: const Y = gen => U(f => gen((...args) => f(f)(...args))) Y(selfFn => arg => selfFn('to infinity and beyond'))

Еще одно решение Y-комбинатора, использующее ссылку на розетт -код (я думаю, что кто-то ранее упоминал ссылку где-то в stackOverflow.

Стрелки для анонимных функций более читабельны:

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

Это может работать не везде, но вы можете использовать его arguments.calleeдля ссылки на текущую функцию.

Итак, факториал можно сделать так:

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