哪些语言支持*递归*函数文字/匿名函数？

现在似乎有不少主流语言支持函数文字.它们也被称为匿名函数,但我不在乎它们是否有名称.重要的是函数文字是一个表达式,它产生一个尚未在别处定义的函数,因此例如在C中,&printf不计算.

编辑添加:如果你有一个真正的函数文字表达式,你应该能够将它传递给一个函数f()或立即将它应用于一个参数,即.(5).

我很好奇哪些语言可以让你编写递归的函数文字.维基百科的" 匿名递归 "文章没有给出任何编程示例.

我们以递归因子函数为例.

以下是我所知道的:

JavaScript/ECMAScript可以用callee:

function(n){if (n<2) {return 1;} else {return n * arguments.callee(n-1);}}

在语言方面很容易letrec,例如Haskell(称之为let):

let fac x = if x<2 then 1 else fac (x-1) * x in fac

Lisp和Scheme中有等价物.请注意,绑定fac是表达式的局部,因此整个表达式实际上是一个匿名函数.

还有其他人吗？

1> John Milliki..：

---

大多数语言通过使用Y组合器来支持它.这是Python中的一个例子(来自cookbook):

# Define Y combinator...come on Gudio, put it in functools!
Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))

# Define anonymous recursive factorial function
fac = Y(lambda f: lambda n: (1 if n<2 else n*f(n-1)))
assert fac(7) == 5040

---

@avernet:我认为那不是一个"真正的"Y组合子,因为Y组合子是一个非常特定形式的表达式,该例子需要一个外部类型,并涉及在表达式中创建该类型的对象,不在Y组合中.

2> FryHard..：

---

C#

阅读Wes Dyer的博客,你会发现@Jon Skeet的答案并不完全正确.我不是语言的天才,但是递归匿名函数和" fib函数真的只是调用本地变量fib引用的委托 "引用博客之间存在差异.

实际的C#答案看起来像这样:

delegate Func Recursive(Recursive r);

static Func Y(Func, Func> f)
{
    Recursive rec = r => a => f(r(r))(a);
    return rec(rec);
}

static void Main(string[] args)
{
    Func fib = Y(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
    Func fact = Y(f => n => n > 1 ? n * f(n - 1) : 1);
    Console.WriteLine(fib(6));                          // displays 8
    Console.WriteLine(fact(6));
    Console.ReadLine();
} 

3> cjm..：

---

你可以在Perl中做到这一点:

my $factorial = do {
  my $fac;
  $fac = sub {
    my $n = shift;
    if ($n < 2) { 1 } else { $n * $fac->($n-1) }
  };
};

print $factorial->(4);

该do块不是绝对必要的; 我把它包括在内以强调结果是一个真正的匿名函数.