c# - 递归到尾递归

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>当我旅行时，我只是没有全神贯注。

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

我知道很难全神贯注，但如果通读它，它应该是有道理的。我们做的第一件事是与 children 一起调用 aux，当前最大值为零；第一次调用 aux 的延续是什么？将其结果添加到头部的成本中，并将其传递给 maximum_path_cost 的延续。我们什么时候这样做？当我们用完整个子节点列表并且没有剩余时。

将其转换为 C# 并使 C# 保证尾递归留作练习。 :)