我的rec函数是尾递归吗？

Question

这个函数是尾递归的吗？

let rec rec_algo1 step J = 
    if step = dSs then J
    else
        let a = Array.init (Array2D.length1 M) (fun i -> minby1J i M J)
        let argmin = a|> Array.minBy snd |> fst
        rec_algo1 (step+1) (argmin::J)

一般来说，有没有一种方式可以正式地检查它？谢谢。

- jliettehk

---

你可以检查编译器是否将其识别为这样（毕竟，这是最重要的），但是不能在不询问编译器进行相应分析通行证的结果（或自己实现并希望它们不比编译器聪明）的情况下进行。 - user395760

这可能回答不了你的第二个问题，但是如果你的函数在递归调用之后没有做任何事情，那么它就是尾递归的。一个明显的标志是：你正在对递归调用的返回值进行操作，而不是返回它。 - Daniel

请参见https://dev59.com/sHRA5IYBdhLWcg3w1BqW。 - Brian

Answer 1

您问如何正式检查这个问题，我来试一下。我们首先必须定义什么是尾递归函数。一个形如以下的递归函数定义：

let rec f x_1 ... x_n = e

如果e内部所有对f的调用都是尾调用，则是尾递归。也就是说，这些调用必须出现在尾部上下文中。一个尾部上下文 C是通过带有空洞[]的项来归纳定义的：

C ::= []
    | e
    | let p = e in C
    | e; C
    | match e with p_1 -> C | ... | p_n -> C
    | if e then C else C

其中e是F#表达式，x是一个变量，p是一个模式。我们应该将其扩展为相互递归的函数定义，但我会把这留作练习。

现在让我们将其应用到你的示例中。函数体中对rec_algo1的唯一调用在这个上下文中：

if step = dSs then J
else
    let a = Array.init (Array2D.length1 M) (fun i -> minby1J i M J)
    let argmin = a|> Array.minBy snd |> fst
    []

由于这是一个尾部上下文，所以该函数是尾递归的。这是函数式程序员的判断方法 - 扫描定义体中的递归调用，然后验证每个调用是否出现在尾部上下文中。更直观的尾调用定义是除了返回调用结果外，没有其他操作。

- petebu

Answer 2

这个函数是尾递归的，从视觉上看我可以确认。

通常情况下很难判断。也许最可靠/实用的方法就是在大量输入上进行检查（确保您正在编译“发布”模式，因为“调试”模式会关闭尾调用以进行更好的调试）。

- Brian

---

谢谢Brian。你对编译模式的评论也很有帮助。 - jliettehk

@Brian - 通过检查函数的相应IL，您能否确定吗？此外，虽然一般的正式检查可能很困难（不可能？），但您能否举出任何难以仅凭肉眼判断的例子？我已经看到很多次说它并不总是容易判断，但我从未见过一个足够复杂的尾递归函数，在这种情况下无法轻松判断。 - Stephen Swensen

我在某个地方看到提到F#团队正在考虑添加一个关键字，让你告诉编译器你打算让一个函数成为尾递归的，这样编译器就可以在实际上不是尾递归时警告你。我认为那将非常方便。 - Joel Mueller

@Stephen - 有两件容易被忽略的事情：（1）仔细查看调用但忘记你在try块中（例如，函数顶部的 use 是否会抵消尾调用？我想是的），以及（2）在进行相互递归时，尾调用一个函数参数，该函数参数会再度尾调用你（特别是当某些参数可能或可能不会部分应用时）。我手头没有例子，但从经验来看，如果您信任自己的眼睛，有时候会感到惊讶。更加罕见的情况是部分信任程序集边界上的相互递归（永远不会尾调用）。 - Brian

@Brian，是的，使用using将“取消”尾递归，因为use id = exprA in exprB等同于函数调用using exprA (fun id -> exprB)，这意味着exprB被计算，但随后必须返回给函数using，该函数最终处于尾位置。 - Sebastian Good

Answer 3

是的，你可以正式证明一个函数是尾递归的。每个表达式规约都有一个尾位置，如果所有递归都在尾位置，则该函数是尾递归的。一个函数可能在一个地方是尾递归的，但在另一个地方不是。

在表达式let pat = exprA in exprB中，只有exprB处于尾位置。也就是说，虽然可以评估exprA，但仍然必须回到以exprA为前提来评估exprB。对于语言中的每个表达式，都有一条规约规则告诉您尾位置在哪里。在ExprA; ExprB中，它再次是ExprB。在if ExprA then ExprB else ExprC中，它既是ExprB也是ExprC等等。

当然，编译器在进行编译时会知道这一点。然而，在F#中提供的许多表达式和编译器进行的许多内部优化（例如，在模式匹配编译期间、计算表达式中，如seq{}或async{}）可能使得知道哪些表达式处于尾位置变得不明显。

实际上，通过一些练习，对于小函数来说，仅需查看嵌套表达式并检查非尾位置的函数调用槽即可确定尾调用。（请记住，尾调用可能是另一个函数！）

- Sebastian Good