首页 / C# / c# – 递归到Tail递归
c# – 递归到Tail递归
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了c# – 递归到Tail递归,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2602字,纯文字阅读大概需要4分钟。
内容图文
![c# – 递归到Tail递归](/upload/InfoBanner/zyjiaocheng/806/94f9c4a9468b4aa5855433d0b24d431c.jpg)
我正在编写一个遍历以找到道路中最长的路径.这段代码的神奇部分是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#保证尾递归仍然是一个练习.
内容总结
以上是互联网集市为您收集整理的c# – 递归到Tail递归全部内容,希望文章能够帮你解决c# – 递归到Tail递归所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。