有趣的递归 lambda 示例

Question

我刚刚偶然发现了一个有趣的递归 lambda 示例，但我真的不明白为什么它以这种方式工作。

rec = lambda x : 1 if x==0 else rec(x-1)*x
f = rec 
rec = lambda x: x+1
print(f(10))

javascript中相同。

var rec = function(a) {
  if (a == 0) return 1;
  return rec(a - 1) * a;
}
var f = rec
rec = function(a) {
  return a + 1;
}
console.log(f(10));

令我惊讶的是，这两个打印结果都是 100 而不是 10！（如我所料）。

为什么重新分配 rec 会改变 f 函数的行为？ rec变量在lambda中捕获的时候，不就是引用了lambda本身吗？

编辑。由于大多数答案都解释了正在发生的事情，让我重新表述这个问题，因为我正在寻找更深入的解释。

所以在第一行声明函数 rec 时，为什么函数体中的 rec 没有绑定到自身？

例如，如果您采用 JavaScript 并按照其中一个答案中的建议以看似 "same" 的方式重写第一行：

var rec =function rec(a) {
    if (a == 0) return 1;
    return rec(a - 1) * a;
};
f = rec;

rec = function (a) {
    return a + 1;
}

console.log(f(10));

这个打印出10个！正如人们所期望的那样。

所以在这种情况下，"inner rec"（在函数体中）绑定到函数名的 rec 而不是查看 rec 变量，并且变量 rec 的重新分配没有改变行为。

所以我真正要问的是那些语言决定在 lambda 中绑定变量的机制。

我自己正在为一个 class 项目编写解释器，我遇到了相同的问题，即何时何地绑定这些变量。所以我想了解这在流行语言中是如何工作的，以实现类似的东西。

Answer 1

这 3 条语句可以总结为一条语句

rec = lambda x : 1 if x==0 else rec(x-1)*x
f = rec 
rec = lambda x: x+1

来自 1 和 2

f = lambda x : 1 if x==0 else rec(x-1)*x

从上面 & 3

f = lambda x : 1 if x==0 else x*x

Answer 2

您可以添加一些 console.log 并查看，首先使用 10 调用 f，然后使用 9 调用 rec，结果是 10 * 10.

var rec = function(a) {
        console.log('f', a);
        if (a == 0) return 1;
        return rec(a - 1) * a;
    };
    f = rec;

rec = function(a) {
    console.log('rec', a);
    return a + 1;
}

console.log(f(10));

保持 rec.

var rec = function rec(a) {
        console.log('f', a);
        if (a == 0) return 1;
        return rec(a - 1) * a;
    };
    f = rec;

rec = function(a) {
    console.log('rec', a);
    return a + 1;
}

console.log(f(10));

Answer 3

我会建议合理使用变量名，这里不需要重新赋值

why it uses second rec not the first one ?

你的函数调用是在重新分配 rec 之后发生的，所以你在 rec 中有最新的值

rec = function(a) {
  return a + 1;
}

var f = function(a) {
  if (a == 0) return 1;
  return rec(a - 1) * a;
}

var rec = function(a) {
  return a + 1;
}
console.log(f(10));

Answer 4

我会为 python 解决这个问题，因为那是我所熟悉的。

首先，这种行为之所以可能，是因为 python（我认为看起来像 javascript）在 late-binding 之后关闭。 further read

后期绑定是指在运行时查找闭包中的名称（不同于在编译时查找名称的早期绑定。）

这允许在运行时间改变行为，方法是重新绑定在运行时间查找的变量（例如像 rec 这样的函数）。

最后一步只是将 lambda 函数转换为等效的 def 语法，这样真实的行为就更清楚了。

代码：

rec = lambda x : 1 if x==0 else rec(x-1)*x
f = rec 
rec = lambda x: x+1
print(f(10))

可以等同于：

第一个：

def somefunc(x):
    return 1 if x==0 else rec(x-1)*x

注意，python 不会抱怨 rec 不存在，即使在干净的 session/kernel 上也是如此，因为它不会在函数定义期间查找值。后期绑定意味着除非调用此函数，否则 python 不关心 rec 是什么。

然后：

rec = somefunc
f = rec

def someotherfunc(x):
    return x + 1

f(10) #3628800

现在我们改变rec函数

rec = someotherfunc

并观察 f 的后续函数调用将使用 late-bound rec，即在函数调用中查找。

f(10) #100

PS。完整代码添加如下：

def somefunc(x):
    return 1 if x==0 else rec(x-1)*x

rec = somefunc

f = rec

def someotherfunc(x):
    return x + 1

f(10) #3628800

rec = someotherfunc

f(10) #100

有趣的递归 lambda 示例

Interesting recursive lambda example

javascript

python

lambda

semantics