我正在编写一个遍历以找到道路中最长的路径.这段代码的神奇部分是segment.Next指的是LINQ,它具有应用于它的特定逻辑,就像不重新访问已访问过的节点一样.因此,不要指出travsel中的缺陷超出范围.

我想要做的是减少堆栈上的调用次数,因为有时路径可能是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>因为我旅行,但我只是没有把头包裹起来.

解决方法:

spender的答案是在没有递归的情况下解决这个问题的实用方法：使用显式堆栈或队列作为帮助器.

原始问题和消费者,在评论中,分别想知道如何在尾递归样式和延续传递样式中执行此算法. (CPS是一种编程风格,其中每个调用都是尾调用.)

为了让您了解该算法的CPS版本的外观,让我(1)大大简化问题,(2)用ML编写解决方案,而不是C#.简化的问题是：

>函数children接受一个节点并生成一堆子节点.
>功能成本给出了遍历单个节点的成本.
>给出的问题是找到最大成本路径的成本.

首先,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做同样的事情.

为简单起见,我们不会将成本和子项转换为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#并使C#保证尾递归仍然是一个练习.