递归转尾递归

Question

我正在编写遍历算法，以查找道路中的最长路径。这段代码的神奇之处在于segment.Next是针对LINQ的，具有特定的逻辑，如不重新访问已经访问过的节点。因此，请不要指出遍历中的缺陷，因为这超出了范围。

我的目标是减少堆栈调用次数，因为有时路径可能会达到5000。我知道我必须使这个递归调用尾递归。

public static IEnumerable<Segment> FindLongestPath(Segment segment)
{
    var rv = new List<Segment> {segment};
    var longestPathLength = 0;
    var longestNextPaths = Enumerable.Empty<Segment>();

    foreach (var n in segment.Next)
    {
        var paths = FindLongestPath(n);
        var length = paths.Sum(p => p.LengthMeters);
        if (length > longestPathLength)
        {
            longestPathLength = length;
            longestNextPaths = paths;
        }
    }

    rv.AddRange(longestNextPaths);

    return rv;
}

我该如何将这个递归调用变成尾递归？我知道我可能需要在遍历时维护 IEnumerable<Segment>，但我还是无法理解它。

- CuriousDeveloper

---

我认为你需要的是，在 var paths = FindLongestPath(n) 调用之后，将 n 添加到“已检查所有子路径”的 ienumberable 中，然后在 FindLongestPath 之前检查 n 是否存在于其中，并且如果存在，则继续循环。当然，这也必须传递到 findlongestpath 中。 - Eric Lizotte

我注意到，你的方法不仅可能会导致堆栈溢出，而且如果没有发生这种情况，它产生的冗余列表数量是巨大的。在这里，最好使用不可变栈作为路径，然后可以将新元素推入其中，而无需重新分配和复制内容。 - Eric Lippert

Answer 1

spender的答案是一种实用的解决这个问题的方法，不使用递归：使用显式栈或队列作为助手。

原始问题和spender在评论中想知道如何以尾递归方式和续延传递方式执行此算法。(CPS是一种编程风格，在其中每个调用都是一个尾调用。)

为了让您了解CPS版本的算法看起来如何，让我(1)大大简化问题，(2)用ML而不是C#编写解决方案。简化后的问题是：

-函数“children”接受一个节点并生成一个子节点堆栈。 -函数“cost”给出遍历单个节点的成本。 -所提供的问题是找到最大成本路径的成本。

首先是在ML中的直接非CPS解决方案:

let rec maximum_path_cost node =
  let rec aux nodes max =
    match nodes with
    | [] -> max
    | head :: tail -> 
       let c = maximum_path_cost head in
       let new_max = if c > max then c else max in
       aux tail new_max
  in
  (cost node) + (aux (children node) 0)

简而言之：我们使用一个递归辅助函数来模拟循环，该函数累计迄今为止看到的最大值。循环条件是“列表是否为空？”如果是，则结果是迄今为止看到的最大值；如果不是，则计算当前项（列表的头部）的成本，将其与最大值进行比较，并在剩余部分上运行循环。

请注意，aux是尾递归的，但maximum_path_cost不是。

在延续传递风格中，maximum_path_cost需要一个延续——在这种情况下，一个接受int类型参数的函数，并且要求它调用该函数并返回结果，而不是直接返回结果。我们将使aux做同样的事情。

为简单起见，我们不会将cost和children转换为CPS。

let rec maximum_path_cost node continuation =
  let rec aux nodes max aux_continuation =
    match nodes with
    | [] -> aux_continuation max
    | head :: tail ->
       let mpcc c = 
         let new_max = if c > max then c else max in
         aux tail new_max aux_continuation
       in
       maximum_path_cost head mpcc
  in
  let ac result =
    continuation ((cost node) + result) 
  in
    aux (children node) 0 ac

我知道这很难理解，但如果你仔细阅读，它应该就有意义了。我们首先使用孩子和当前最大值为零来调用aux；第一次调用aux的后续步骤是什么？将其结果添加到头部成本中，并将其传递给maximum_path_cost的继续部分。什么时候做到这一点？当我们已经遍历完整个子节点列表并没有剩下任何一个时。将其翻译成C#语言并保证尾递归，则需要自己动手完成，:)。

- Eric Lippert

Answer 2

使用尾递归实现这个功能将会很棘手，因为你需要将继续函数作为委托传递以进行后递归处理。对于不熟悉函数式风格的人来说，代码看起来可能很丑陋。

似乎你的主要动机是避免调用栈溢出。通过采用非递归方法，使用显式的Queue<T>/Stack<T>（取决于你想要遍历深度还是广度），而不是从非尾递归方法调用中获取的隐式堆栈，意味着你的堆栈仅受可用内存的限制。

以下内容可以帮助你开始实现这个功能：

public static IEnumerable<Segment> FindLongestPath(Segment segment)
{
    var queue = new Queue<Segment>(); //or a Stack<Segment> with Push and Pop
    queue.Enqueue(segment);

    while(queue.Any())
    {
        var currentSegment = queue.Dequeue();
        foreach(var seg in currentSegment.Next)
        {
            queue.Enqueue(seg);
        }
        //process currentSegment
    }
}

- spender

---

@CuriousDeveloper：这绝对是正确的方法；如果您想了解更多信息，可以查阅显式栈和队列如何用于深度优先和广度优先遍历。 - Eric Lippert

@CuriousDeveloper 我也对CPS递归的解决方案感兴趣，但作为一位受伤的父母，今天我也很难理解它。 - spender

@EricLippert 这个我发的问题得到了您的回答，让我开始思考… 我本来在考虑提出一个问题，但既然您在这里… 我知道状态机的成本很高，但我想到一个方法：使用await或yield可以使得continuation不像是continuation。 这样做可行吗？如果可以的话，它是否属于尾递归？ - spender

@spender：从理论上讲，是的；通过巧妙地使用await，您将获得“无栈递归”。但实践中存在一些困难。 await 检查返回的任务是否已完成；如果是，则它会继续执行，这样您就可以获得带有大量额外成本的正常递归算法。如果没有完成，那么什么将导致它在未来完成？ - Eric Lippert

我认为这篇文章很有帮助 https://dev59.com/oHRB5IYBdhLWcg3wNk93 - Kixoka