相互递归函数中的尾递归

Question

我有以下代码：

let rec f n =
    if n < 10 then "f" + g (n+1) else "f"
and g n =
    if n < 10 then "g" + f (n+1) else "g"

我想让这些相互递归的函数尾递归优化。我尝试了以下方法：

let rec fT n = 
    let rec loop a = 
        if n < 10 then "f" + gT (a) else "f"
    loop (n + 1) 
and gT n =
    let rec loop a = 
        if n < 10 then "g" + fT (a) else "g"
    loop (n + 1)

这是正确的尾递归版本吗？如果没有，将不胜感激正确方向的提示。

编辑（第二次尝试解决方案）：

let rec fA n = 
    let rec loop n a = 
        if n < 10 then loop (n + 1) ("f" + a) else a
    loop n "f"
and gA n =
    let rec loop n a = 
        if n < 10 then loop (n + 1) ("g" + a) else a
    loop n "g"

编辑（第三次尝试解决方案）：

let rec fA n a = 
    if n < 10 then gA (n + 1) (a + "f") else a
and gA n a =
    if n < 10 then fA (n + 1) (a + "g") else a

编辑（正确的解决方案）：

let rec fA n a = 
    if n < 10 then gA (n + 1) (a + "f") else (a + "f")
and gA n a =
    if n < 10 then fA (n + 1) (a + "g") else (a + "g")

Answer 1

您的解决方案绝对不是尾递归。

"Tail-recursion" 是这样的递归，其中每个递归调用都是函数所做的 last 事情。这个概念很重要，因为它意味着运行时可以选择不在调用之间保留堆栈帧：因为递归调用是最后一件事，并且调用函数在此之后不需要做任何其他事情，运行时可以跳过 return 对调用函数的控制，并让被调用函数 return 有权访问顶级调用者。这允许表达任意深度的递归算法而不用担心运行出栈 space.

然而，在您的实现中，函数 fT.loop 调用函数 gT，然后将 "f" 添加到任何 gT returned。 "f" 的前置发生在 gT 已经 returned 之后，因此对 gT 的调用是 not fT.loop 做的最后一件事。因此，它不是尾递归的。

为了将 "regular" 递归转换为 "tail" 类型，可以这么说，您必须 "turn the logic inside out"。让我们看一下函数 f：它调用 g，然后将 "f" 添加到 g return 之前。这个"f"前缀就是整个"contribution"函数f在总的计算中。现在，如果我们想要尾递归，这意味着我们不能在递归调用之后进行 "contribution" 。这意味着贡献必须在之前发生。但是，如果我们在调用之前进行贡献，之后什么都不做，那么我们如何避免丢失该贡献呢？唯一的方法是将贡献作为参数传递给递归调用。

这是尾递归计算背后的一般思想：我们不是等待嵌套调用完成然后向输出添加一些内容，而是先进行添加并将已经 "added so far" 的内容传递给递归调用。

回到您的具体示例：由于 f 的贡献是 "f" 字符，因此需要将此字符添加到已计算的内容中 "so far" 并将其传递给递归调用，然后将执行相同的操作，依此类推。 "so far" 参数应该具有 "compute whatever you were going to compute, and then prepend my 'so far' to that".

的语义

既然你只要求了一个"hint"，这显然是作业（如果我错了请原谅我），我不会post实际代码。如果您希望我这样做，请告诉我。

Answer 2

我赞同你的尝试绝对没有将递归放在尾部位置的观察结果

我将如何处理将递归移动到尾部位置将使用延续。为此，我们必须实现具有连续参数的 fk 和 gk 变体，然后 f 和 g 可以使用 fk 和gk分别

我不是 F# 专家，但我可以用 JavaScript 非常简单地说明这一点。我通常不会 post 使用不同的语言来回答，但由于语法非常相似，我认为它会对你有所帮助。它还具有额外的好处，您可以运行在浏览器中查看此答案是否有效

// f helper
let fk = (n, k) => {
  if (n < 10)
    return gk(n + 1, g => k("f" + g))
  else
    return k("f")
}
    
// g helper
let gk = (n, k) => {
  if (n < 10)
    return fk(n + 1, f => k("g" + f))
  else
    return k("g")
}
    
let f = n =>
  fk(n, x => x)

let g = n =>
  gk(n, x => x)
  
console.log(f(0))  // fgfgfgfgfgf
console.log(g(0))  // gfgfgfgfgfg
console.log(f(5))  // fgfgfg
console.log(g(5))  // gfgfgf
console.log(f(11)) // f
console.log(g(11)) // g

相互递归函数中的尾递归

Tail recursion in mutually recursive functions

recursion

f#

f#-interactive