javascript:递归匿名函数?

IT技术 javascript recursion scope anonymous-function
2021-01-27 05:35:28

假设我有一个基本的递归函数:

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

我想要一种方法来调用调用这个函数的函数......我在某处看到过脚本(我不记得在哪里)可以告诉你被调用函数的名称,但我不记得任何一个现在的信息。

6个回答

可以为函数命名,即使您将函数创建为值而不是“函数声明”语句。换句话说:

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

是一个堆栈溢出的递归函数。现在,也就是说,您可能不想这样做,因为 Javascript 的各种实现存在一些奇怪的问题。注意——这是一个相当古老的评论;Kangax 的博客文章中描述的一些/许多/所有问题可能会在更现代的浏览器中得到修复。)

当您给出这样的名称时,该名称在函数外部不可见(嗯,它不应该是;这是奇怪之处之一)。这就像 Lisp 中的“letrec”。

至于arguments.callee,这在“严格”模式下是不允许的,通常被认为是一件坏事,因为它使一些优化变得困难。它也比人们预期的要慢得多。

编辑——如果你想要一个可以调用自己的“匿名”函数的效果,你可以做这样的事情(假设你将函数作为回调或类似的东西传递):

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

这样做是用一个漂亮的、安全的、不被破坏的 IE 函数声明语句定义一个函数,创建一个名称不会污染全局命名空间的局部函数。包装器(真正匿名)函数只返回该本地函数。

我们是否可以避免使用 ES5 sctrict 以另一种方式污染全局命名空间(我还没有深入阅读 ES5)?
2021-03-23 05:35:28
我想不可能(() => { call_recursively_self_here() })()递归地使用和调用自己,对吗?我必须给它一个名字。
2021-04-08 05:35:28
@Pointy 也许有些黑客会找到应用程序;)
2021-04-08 05:35:28
@pointy 你能看看这个问题吗。stackoverflow.com/questions/27473450/...
2021-04-10 05:35:28
@Qwerty 好吧,您可以在我的回答中执行类似于最后一个示例的操作。将箭头函数绑定到包装函数中的局部变量,以便您的箭头函数可以使用变量名称引用自身。然后包装器将返回变量(指的是箭头函数)。
2021-04-14 05:35:28

人们在评论中谈论 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();
  }
})());

关于此解决方案需要注意的最重要的一点是您不应该使用它。

不要忘记提到这个函数不是堆栈安全的。仅循环几千次就会导致堆栈溢出。
2021-03-19 05:35:28
嗨,我建议稍微“更干净”的修改,因为 .apply(null,arguments) 对我来说似乎很难看: var Y = function (gen) { return (function(f) { return f(f); }(function(f) { return gen(function(x) { return f(f)(x); }); })); 或者等效地 (( function(x){return y} equals (x => y) )) 通过使用箭头符号(有效的 js 代码): var Y = gen => ( f => f(f) ) ( f = > gen ( x => f(f)(x) ) )
2021-04-02 05:35:28
“关于这个解决方案需要注意的最重要的一点是你不应该使用它。” 为什么?
2021-04-03 05:35:28
它不会很快。实际使用起来很丑陋(虽然概念上很漂亮!)。您不必为您的函数指定标签或变量名称(我不明白为什么会有问题),但您仍然为其指定一个名称作为传递给 Y 的外部函数的参数。所以您不必经历这些困难,什么都得到。
2021-04-13 05:35:28

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组合子应用于自身时,它返回一个等待第一个输入的函数。如果我们给它起个名字,就可以有效地使用 lambdas(匿名函数)构造递归函数

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-combinator 建立在 U-combinator 的基础上,去掉了那个乏味的部分。这是一件好事,因为消除/降低复杂性是我们制作函数的主要原因

首先,让我们推导出我们自己的 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-combinator 相比如何。注意,要重复,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


具有 1 个以上参数的 U 和 Y 组合器

在上面的例子中,我们看到了如何循环并传递参数来跟踪计算的“状态”。但是如果我们需要跟踪额外的状态呢?

我们可以使用像数组这样的复合数据……

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

但这很糟糕,因为它暴露了内部状态(计数器ab)。如果我们能打电话fibonacci (7)得到我们想要的答案,那就太好了。

使用我们对柯里化函数(一元(1 参数)函数的序列)的了解,我们可以轻松实现我们的目标,而无需修改Y或依赖复合数据或高级语言功能的定义。

fibonacci仔细看看下面的定义我们立即申请0and 1which 分别绑定到ab现在斐波那契只是等待提供最后一个参数,该参数将绑定到x当我们递归时,我们必须调用f (a) (b) (x)(not 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组合子(rangereduce)和衍生物reducemap

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)使用匿名函数递归计算

哦,天哪,javascript 中有很多 Haskell
2021-03-15 05:35:28

使用“匿名对象”可能是最简单的:

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

您的全球空间是完全未受污染的。这很简单。并且您可以轻松利用对象的非全局状态。

您还可以使用 ES6 对象方法使语法更简洁。

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

我不会将其作为内联函数执行。它突破了品味的界限,并没有真正让你得到任何东西。

如果您真的必须这样做,arguments.callee就像 Fabrizio 的回答一样。然而,这通常被认为是不可取的,并且在 ECMAScript Fifth Edition 的“严格模式”中是不允许的。尽管 ECMA 3 和非严格模式不会消失,但在严格模式下工作有望实现更多可能的语言优化。

还可以使用命名的内联函数:

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

然而,最好避免命名内联函数表达式,因为 IE 的 JScript 对它们做了一些不好的事情。在上面的例子中foo错误地污染了 IE 中的父作用域,而父作用域foo是一个单独的实例,可以foo看到里面的foo

将其放入内联匿名函数的目的是什么?如果您只想避免污染父作用域,您当然可以将第一个示例隐藏在另一个自调用匿名函数(命名空间)中。你真的需要nothing每次围绕递归创建一个新副本吗?使用包含两个简单的相互递归函数的命名空间可能会更好。

@Peter: kangax.github.com/nfe(尤其是“JScript 错误”)比你想知道的更多。它最终在 IE9 中修复(但仅限于 IE9 标准模式)。
2021-03-15 05:35:28
如果污染真的是这里的一个问题,那么简单的前/后缀怎么样?考虑到它不在全局范围内(即使函数是顶级的,他应该已经有一个匿名函数来包装他的整个代码),这样的名称真的不太可能recur_foo与父范围内的函数发生冲突(或生病) -用过的) 。
2021-03-17 05:35:28
+1 表示诗意,"pushing against the boundaries of good taste"-(嗯,还有很好的信息)。
2021-03-23 05:35:28
非常有趣 - jsfiddle.net/hck2A - 在这种情况下,IE 确实会污染父级,就像你说的那样。从来没有意识到这一点。
2021-04-03 05:35:28
我同意,命名函数比 arguments.callee 更适合,不仅适用于 ecmascript 严格模式,而且适用于优化问题,因为在每次递归时,他都需要获得对被调用者的引用(这可能会降低执行速度)
2021-04-06 05:35:28