我的rec函数尾递归吗？

这个函数是否是尾递归的？我的rec函数尾递归吗？

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)

一般情况下，是有办法正式检查呢？

谢谢。

来源

2011-04-27 jliettehk

你可以有条不紊地检查编译器是否认识到它（毕竟，这是最重要的），但不是不向编译器询问相应分析过程的结果（或者实施一些你自己并希望它们不是更聪明比编译器）。 – delnan 2011-04-27 19:49:04

这可能会也可能不会回答你的第二个问题，但是，如果你的函数在递归调用后没有做任何事情，那么它是尾递归的。一个迹象表明它不是尾递归的：你正在做递归调用的返回值，除了返回它。 – Daniel 2011-04-27 21:04:28

参见http://stackoverflow.com/questions/806712/how-do-i-know-if-a-function-is-tail-recursive-in-f – Brian 2011-04-27 22:16:33

这个函数是尾递归的;我可以通过目测来判断。

通常情况下并不总是很容易分辨。也许最可靠/实用的方法就是在大量输入中检查它（并确保在“释放”模式下进行编译，因为“调试”模式会关闭尾部调用以进行更好的调试）。

来源

2011-04-27 19:55:30 Brian

谢谢布莱恩。您对编译模式的评论也很有帮助。 – jliettehk 2011-04-27 20:00:29

@布莱恩 - 你能通过检查相应的IL来判断函数吗？另外，虽然普通的正式支票可能很难（不可能？），但是您能否举例说明仅仅通过目测难以分辨的地方？我已经看到它多次说过，这并不总是很容易说出来，但我从来没有见过一个复杂的尾递归函数，它不容易分辨。 – 2011-04-27 20:11:18

某处我看到F＃团队正在考虑一个未来的关键字，它会让你告诉编译器你想要一个函数是尾递归的，这样编译器可以警告你它是否真的不是。我认为这真的很方便。 – 2011-04-27 20:29:45

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

在表达式let pat = exprA in exprB中，只有exprB处于尾部位置。也就是说，尽管您可以评估exprA，但您仍然必须回头评估exprB和exprA。对于语言中的每个表达式，都有一个减少规则，告诉你尾部位置在哪里。在ExprA; ExprB它再次ExprB。在if ExprA then ExprB else ExprC这是ExprB和ExprC等等。

编译器当然知道这一点。然而，F＃中可用的许多表达式以及编译器进行的许多内部优化，例如，在模式匹配编译期间，计算表达式如seq{}或async{}可以使得知道哪些表达式处于尾部位置不明显。

实际上，通过一些实践，小功能很容易通过查看嵌套表达式并检查不在尾部位置的槽来进行函数调用来确定尾部调用。（请记住，尾巴呼叫可能是另一个功能！）

来源

2011-04-27 22:36:32

你问我们如何正式检查这个，所以我会刺伤。我们首先必须定义函数是尾递归的意思。形式

let rec f x_1 ... x_n = e

的递归函数的定义是尾递归如果f内e所有呼叫都尾调用 - 即。发生在尾部情况下。甲尾上下文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 
    []

而且因为这是一个尾背景下，功能是尾递归。这就是函数程序员如何看待它 - 扫描递归调用定义的主体，然后验证每个调用是否发生在尾部上下文中。一个更直观的尾部呼叫定义是除了返回呼叫之外没有其他任何操作的结果。

来源

2011-04-28 10:45:19 petebu

我的rec函数尾递归吗？

回答

相关问题