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

Question

如今，似乎有不少主流语言支持函数文字。它们也被称为匿名函数，但我不在乎它们是否有名字。重要的是，函数文字是一个表达式，它产生一个尚未在其他地方定义的函数，例如在 C 中，&printf不计算在内。

编辑添加：如果你有一个真正的函数文字表达式<exp>，你应该能够将它传递给一个函数f(<exp>)或立即将它应用于一个参数，即。<exp>(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是表达式的局部变量，因此整个表达式实际上是一个匿名函数。

还有其他人吗？

score 16 · Accepted Answer

大多数语言通过使用Y 组合器来支持它。这是 Python 中的一个示例（来自食谱）：

# 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

score 7 · Accepted Answer

C＃

阅读Wes Dyer 的博客，您会发现 @Jon Skeet 的回答并不完全正确。我不是语言天才，但递归匿名函数和“ fib 函数实际上只是调用局部变量 fib 引用的委托”以从博客中引用是有区别的。

实际的 C# 答案如下所示：

delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);

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

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

score 5 · Accepted Answer

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

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

print $factorial->(4);

该do块不是绝对必要的；我包含它是为了强调结果是一个真正的匿名函数。

score 4 · Accepted Answer

好吧，除了您已经提到的 Common Lisp ( labels) 和 Scheme ( ) 之外，JavaScript 还允许您命名一个匿名函数：letrec

var foo = {"bar": function baz() {return baz() + 1;}};

这比使用callee更方便。function（这与顶层不同；后者会导致名称也出现在全局范围内，而在前一种情况下，名称仅出现在函数本身的范围内。）

score 4 · Accepted Answer

在 Perl 6 中：

my $f = -> $n { if ($n <= 1) {1} else {$n * &?BLOCK($n - 1)} }
$f(42);  # ==> 1405006117752879898543142606244511569936384000000000

score 2 · Accepted Answer

您在这里混淆了一些术语，函数文字不必是匿名的。

在 javascript 中，区别取决于函数是写成语句还是表达式。关于这个问题的答案中的区别有一些讨论。

假设您将示例传递给函数：

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

这也可以写成：

foo(function fac(n){if (n<2) {return 1;} else {return n * fac(n-1);}});

在这两种情况下，它都是函数文字。但请注意，在第二个示例中，名称并未添加到周围的范围内——这可能会造成混淆。但这并没有被广泛使用，因为一些 javascript 实现不支持这个或者有一个错误的实现。我也读过它更慢。

匿名递归又是不同的东西，当一个函数在没有引用自身的情况下递归时，已经提到了 Y Combinator。在大多数语言中，没有必要这样做，因为有更好的方法可用。这是一个 javascript 实现的链接。

score 2 · Accepted Answer

2

F#有“let rec”

于 2008-10-01T05:48:40.957 回答

score 1 · Accepted Answer

在 C# 中，您需要声明一个变量来保存委托，并将 null 分配给它以确保它已明确分配，然后您可以从分配给它的 lambda 表达式中调用它：

Func<int, int> fac = null;
fac = n => n < 2 ? 1 : n * fac(n-1);
Console.WriteLine(fac(7));

我想我听说 C# 团队正在考虑更改明确分配的规则以使单独的声明/初始化变得不必要，但我不会发誓。

每种语言/运行时环境的一个重要问题是它们是否支持尾调用。在 C# 中，据我所知，MS 编译器不使用tail.IL 操作码，但在某些情况下，JIT可能会对其进行优化。显然，这很容易区分工作程序和堆栈溢出。（最好对此有更多的控制权和/或保证它何时会发生。否则，在一台机器上运行的程序可能会以难以理解的方式在另一台机器上失败。）

编辑：正如FryHard指出的，这只是伪递归。简单到足以完成工作，但 Y-combinator 是一种更纯粹的方法。我在上面发布的代码还有另一个警告：如果更改的值fac，任何尝试使用旧值的东西都会开始失败，因为 lambda 表达式已经捕获了fac变量本身。（当然，为了正常工作，它必须这样做......）

score 1 · Accepted Answer

似乎 Mathematica 还允许您定义递归函数#0来表示函数本身，如：

(expression[#0]) &

例如阶乘：

fac = Piecewise[{{1, #1 == 0}, {#1 * #0[#1 - 1], True}}] &;

这与#i引用第 i 个参数的表示法以及脚本是它自己的第 0 个参数的 shell 脚本约定一致。

score 1 · Accepted Answer

您可以在 Matlab 中使用匿名函数执行此操作，该函数使用 dbstack() 自省来获取自身的函数文字，然后对其进行评估。（我承认这是作弊，因为 dbstack 可能应该被认为是语言外的，但它在所有 Matlabs 中都可用。）

f = @(x) ~x || feval(str2func(getfield(dbstack, 'name')), x-1)

这是一个从 x 开始倒数然后返回 1 的匿名函数。它不是很有用，因为 Matlab 缺少 ?: 运算符并且不允许匿名函数内部的 if 块，因此很难构造基本案例/递归步骤形式。

您可以通过调用 f(-1); 来证明它是递归的；它将倒数到无穷大并最终引发最大递归错误。

>> f(-1)
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

您可以直接调用匿名函数，无需将其绑定到任何变量，只需将其直接传递给 feval。

>> feval(@(x) ~x || feval(str2func(getfield(dbstack, 'name')), x-1), -1)
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Error in ==> create@(x)~x||feval(str2func(getfield(dbstack,'name')),x-1)

为了使它有用，您可以创建一个单独的函数来实现递归步骤逻辑，使用“if”来保护递归案例不被评估。

function out = basecase_or_feval(cond, baseval, fcn, args, accumfcn)
%BASECASE_OR_FEVAL Return base case value, or evaluate next step
if cond
    out = baseval;
else
    out = feval(accumfcn, feval(fcn, args{:}));
end

鉴于此，这里是阶乘。

recursive_factorial = @(x) basecase_or_feval(x < 2,...
    1,...
    str2func(getfield(dbstack, 'name')),...
    {x-1},...
    @(z)x*z);

你可以在没有绑定的情况下调用它。

>> feval( @(x) basecase_or_feval(x < 2, 1, str2func(getfield(dbstack, 'name')), {x-1}, @(z)x*z), 5)
ans =
   120

score 0 · Accepted Answer

匿名函数存在于带有 lambda 的 C++0x 中，它们可能是递归的，尽管我不确定匿名。

auto kek = [](){kek();}

score 0 · Accepted Answer

Delphi 在 2009 版中包含匿名函数。

来自http://blogs.codegear.com/davidi/2008/07/23/38915/的示例

type
  // method reference
  TProc = reference to procedure(x: Integer);               

procedure Call(const proc: TProc);
begin
  proc(42);
end;

利用：

var
  proc: TProc;
begin
  // anonymous method
  proc := procedure(a: Integer)
  begin
    Writeln(a);
  end;               

  Call(proc);
  readln
end.

score 0 · Accepted Answer

我认为这可能不是您想要的，但在 Lisp 中，“标签”可用于动态声明可递归调用的函数。

(labels ((factorial (x) ;define name and params
    ; body of function addrec
    (if (= x 1)
      (return 1)
      (+ (factorial (- x 1))))) ;should not close out labels
  ;call factorial inside labels function
  (factorial 5)) ;this would return 15 from labels

score 0 · Accepted Answer

因为我很好奇，我实际上试图想出一种在MATLAB中做到这一点的方法。可以做到，但看起来有点像 Rube-Goldberg 式的：

>> fact = @(val,branchFcns) val*branchFcns{(val <= 1)+1}(val-1,branchFcns);
>> returnOne = @(val,branchFcns) 1;
>> branchFcns = {fact returnOne};
>> fact(4,branchFcns)

ans =

    24

>> fact(5,branchFcns)

ans =

   120

score 0 · Accepted Answer

'看来你对匿名函数的理解是错误的，这不仅仅是关于运行时的创建，它也是关于范围的。考虑这个 Scheme 宏：

(define-syntax lambdarec
  (syntax-rules ()
    ((lambdarec (tag . params) . body)
     ((lambda ()
       (define (tag . params) . body)
        tag)))))

这样：

(lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1)))))

评估为真正的匿名递归阶乘函数，例如可以像这样使用：

(let ;no letrec used
    ((factorial (lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1)))))))
  (factorial 4)) ; ===> 24

但是，使其匿名的真正原因是，如果我这样做：

((lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1))))) 4)

该函数随后从内存中清除并且没有范围，因此在此之后：

(f 4)

要么发出错误信号，要么将绑定到 f 之前绑定的任何内容。

在 Haskell 中，实现相同目的的一种特别方法是：

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

再次不同的是，这个函数没有作用域，如果我不使用它，Haskell 是 Lazy 的效果与空代码行相同，它是真正的字面意思，因为它与 C 代码具有相同的效果：

3;

一个字面数字。即使我之后立即使用它，它也会消失。这就是文字函数的意义所在，而不是在运行时创建本身。

score 0 · Accepted Answer

Clojure 可以做到这一点，因为它fn需要一个专门用于此目的的可选名称（该名称不会超出定义范围）：

> (def fac (fn self [n] (if (< n 2) 1 (* n (self (dec n))))))
#'sandbox17083/fac
> (fac 5)
120
> self
java.lang.RuntimeException: Unable to resolve symbol: self in this context

如果它恰好是尾递归，那么recur是一种更有效的方法：

> (def fac (fn [n] (loop [count n result 1]
                     (if (zero? count)
                       result
                       (recur (dec count) (* result count))))))

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

16 回答 16

Related

Reference

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