问题标签 [recursion]

我需要在复杂的图形结构中找到一条或多条路径。该图是使用与此类似的东西构建的：

使这变得复杂的是节点可以引用回更早的节点。例如，

A -> C -> E -> A

我需要做的是获取一个堆栈列表，这些堆栈代表通过节点的路径，直到我到达具有特定值的节点。由于可能有一些非常大的路径可用，我们可以尝试最多的节点。

有没有人有办法构建这个（或类似的东西）？我过去做过递归，但出于某种原因，我脑子里全是放屁。我的问题指定了一个 lambda 表达式，但不一定需要使用 lambda。我将不胜感激任何解决方案。

旁注：我从 aku 对这个递归问题的出色回答中提升了课程。虽然下面显示的他优雅的解决方案遍历了树结构，但它似乎没有足够的灵活性来做我需要的事情（例如，关闭圆形路径并跟踪成功的路径）。

编辑：

根据下面评论和答案的输入，我在 CodeProject 中找到了一个很好的解决方案。它使用 A* 路径查找算法。 链接在这里。

在我的职业生涯中，我遇到过几次这个问题，并且从来没有对这个解决方案感到非常满意，并且在我在 ASP.Net MVC、C#、SQL Server 2008 中做的一个项目中再次遇到了这个问题：

想象一下，我有一个 Person 类型（类）。我还有扩展 Person 的类型 Mother 和 Father。父亲和母亲非常相似：他们都有一个名为“Children”的属性，它是一个 Person 类型的集合。“人”可以用基本的 Person 类、Mother 类或 Father 类来表示。从这个例子你可以看到我有继承（is-a）和关联（has-a）关系。

我想使用这些 OO 类型在 SQL Server 中构建和存储家谱。我想我想要这 3 张表：Person、Mother 和 Father。每个对象在 Person 中都有一个条目，如果合适的话，可能还有在 Mother 或 Father 中的条目（与 Person 有 FK 关系）。此外，我将需要一些人行横道表来存储母亲记录与任何子记录之间的关系，与父亲相同。

这听起来像是一个很好的存储策略吗？

你将如何有效地查询这个深度和广泛的家谱？

我被挂断的问题是在树中返回和给定节点的数据的多态性。如果这只是 Person 对象的树，我会使用Recursive Common Table Expression。但是对于任何给定节点，可能会返回 3 种不同形状的数据，我想将其映射到 C# 中的 3 种 OO 类型之一。我显然可以在 C# 或存储过程中进行递归，但我对过去此类解决方案的性能不太满意。另外，如何自然地插入记录？由于 SQL Server 中的 FK 关系强制，我过去总是必须以正确的顺序插入（人，然后是父亲或母亲）。

是否有一个框架可以为我处理这种类型的 ORM？

编辑：

为了清楚起见，我需要的解决方案是检索整个家谱以进行显示，并能够向家谱添加和编辑节点。我认为最好的解决方案是在一棵深树中的一个查询中执行此操作。我要问的是如何设计模式、存储和检索？

所以我在 Python 中编写了一个简单的二叉树并遇到了 [...]

我不认为这与 Ellipsis 对象有关，它似乎与无限循环有关（由于 Python 的浅拷贝？）。但是，这个无限循环的来源以及为什么在访问时扩展时它没有得到扩展是我完全不知道的

使用 a+b 的版本

使用 [a,b] 的版本

那么究竟是什么[...]？

我正在阅读“A Gentle Introduction to Haskell”，并在早期使用了这个示例，该示例在 GHC 中运行良好，但在我的大脑中却非常糟糕：

和调用代码：
take 10 reqs

我看到它的方式是reqs被调用，产生一个调用clientargs 0 和resps. 因此resps现在不需要被调用......这又会reqs再次调用？这一切似乎都是无限的......如果有人能详细说明它是如何工作的，我将不胜感激！

我试图弄清楚如何在树节点中实现一个函数，该函数返回其所有后代叶子（无论是直接的还是间接的）。但是，我不想传递将递归放置叶节点的容器（树可能很大），而是我想使用生成器来遍历树。我尝试了几种方法，但到目前为止没有一种方法有效。这是我最接近可能的解决方案的一个：

但这也不起作用。我究竟做错了什么？如果同一个函数中有一个 yield 语句，似乎递归调用 .EnumerateLeaves 将不起作用。

任何帮助将不胜感激。提前致谢。

编辑：我忘了提到一个分支可以有叶子或分支作为孩子，因此递归。

我刚刚阅读了 Mark Lutz 的“Learning Python”并遇到了这个代码示例：

它被识别为循环数据结构。

所以我想知道，这是我的问题：

在现实生活中的编程中使用的“循环数据结构”是什么？

似乎有点混乱，我认为这源于非常简短的代码示例......这里还有几行使用相同的对象 L

Perl 的Data::Rmap允许您在数据结构列表上递归评估 BLOCK（本地设置 $_ 到每个元素）并返回由此类评估结果组成的列表。$_ 可用于修改元素。

这对于迭代嵌套散列或散列数组的层次结构等非常有用。

我在递归 C++ 程序中分配和释放内存时遇到问题。因此，如果不使用自动内存管理解决方案，我想知道是否有人可以帮助我解决我遇到的内存泄漏问题。

下面的代码基本上解释了这个问题（虽然这是一个人为的例子，请纠正我所做的任何错误或简化）。

保存数字值的数字类：

执行递归的两个函数：

如您所见，递归函数中分配的内存已泄漏，但我不确定根据递归的性质我可以从哪里释放这些内存？

假设您的组织中有一个分支表。其中一些是“主要”分支机构，而另一些则是延伸到主要分支机构的卫星办公室。除了这种只影响系统中一些事情的区别之外，分支都是对等的并且具有相同的属性（地址等）。对此建模的一种方法是在如下表中：

Where is_satellite_office= 1 如果这条记录是另一个分支的附属，并且satellite_to_branch_id指的是你是哪个分支的附属，如果有的话。

对表施加约束很容易，以便这两列在任何给定记录上达成一致：

但是，我真正想要的是一种方法来保证这种递归只深入一层......也就是说，如果我指向一个分支作为我的父级，它本身一定没有父级，并且它的值is_satellite_office必须是0. 换句话说，我并不真正想要一个完全递归的树结构，我只是想将其限制为单个父/子关系。这就是我要编写代码的方式，如果有一种方法可以在数据库中强制执行它不会像完全废话一样执行，我愿意。

有任何想法吗？我正在研究 MSSQL 2005，但首选通用（非供应商特定）解决方案。并且不需要应用触发器，除非真的没有其他方法可以做到这一点。

编辑：要清楚，satellite_to_branch_id是指向同一分支表中另一条记录的递归指针。我知道我可以删除is_satellite_office BIT并依赖IsNull(satellite_to_branch_id)给我相同的信息，但我发现明确一点更清楚，除此之外，这不是问题的要点。我真的在寻找一种纯 SQL 约束方式来防止递归深度大于 1。

换句话说，我可以做类似的事情吗

除了N次？换句话说，当调用创建循环的方法时，给它一些参数N，然后该方法会创建N个这些循环嵌套在另一个？

当然，这个想法是应该有一种“简单”或“通常”的方式来做这件事。我已经有了一个非常复杂的想法。