递归到尾递归

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

使用尾递归执行此操作将很棘手，因为您需要将延续作为委托来处理，以便执行 post-递归处理。对于不熟悉函数式风格的人来说，代码看起来会很糟糕。

看来您的主要动机不是破坏调用堆栈。您可以通过采用非递归方法来减少 "brain-burn" 。使用显式 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
    }
}

Answer 2

spender 的回答是无需递归即可解决此问题的实用方法：使用显式堆栈或队列作为助手。

原题和spender在评论中分别想知道如何以尾递归风格和连续传递风格来做这个算法。（CPS 是一种编程风格，其中每次调用都是尾调用。）

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

函数 children 获取一个节点并生成 child 个节点的堆栈。
函数cost给出了遍历单个节点的代价。
给出的问题是求最大成本路径的成本。

首先，一个直接的 non-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)

简而言之：我们用一个递归辅助函数模拟一个循环，该函数累加到目前为止看到的最大值。循环条件是 "is the list empty?" 如果是，那么结果就是目前看到的最大值；如果不是，那么我们计算当前项目（列表的头部）的成本，将其与最大值进行比较，然后运行在尾部循环。

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

在连续传递样式中，maximum_path_cost 采用连续（在本例中为采用 int 的函数）并且需要使用其结果调用该函数，而不是返回。我们会让 aux 做同样的事情。

为简单起见，我们不会将成本和 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 的延续。我们什么时候这样做？当我们运行遍历 child 个节点并剩下 none 时。

将其翻译成 C# 并使 C# 保证尾递归留作练习。 :)

递归到尾递归

Recursive to Tail recursive

c#

traversal