递归到尾递归
我正在写一篇文章，目的是寻找一条路中最长的一条路。这段代码的神奇部分是segment.Next，它有特定的逻辑应用于它，比如不重新访问已经访问过的节点。因此，不要指出流星中的缺陷，因为这超出了范围。
我想要做的是减少堆栈上的调用数量，因为有时路径可能是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>，但我只是没有把头绕在它周围。
回答 2
Stack Overflow用户
发布于 2017-06-09 15:58:03
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的函数--并且需要用其结果调用该函数，而不是返回。我们会让辅警也这么做。
为了简单起见，我们不会将成本和子级转换为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，当前的最大值为零；第一次呼叫的延续是什么？将其结果添加到头的成本中，并将其传递给maximum_path_cost的延续。我们什么时候这么做？当我们运行了整个子节点列表而没有一个节点的时候。
将其转换为C#并使C#保证尾部递归是一个练习。:)
Stack Overflow用户
发布于 2017-06-09 14:37:44
使用尾递归进行此操作将非常棘手，因为您需要以委托的身份传递连续操作，以便完成后递归处理。对于那些不熟悉功能风格的人来说，这段代码看起来相当讨厌。
你在这里的主要动机似乎不是破坏调用堆栈。你可以采取非递归的方法来减少你的“大脑灼伤”。使用显式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
}
}https://stackoverflow.com/questions/44459756
复制相似问题
腾讯云开发者
