问题标签 [recursion]

下面是一个相当简单的函数，它计算机器上有多少文件。调用“C:\”，运行大约需要 5 秒。除非我有一段时间没有运行它或者首先运行一个 ram-clearing 程序，在这种情况下它需要 60 秒或更长时间。我不会认为它可能是缓存，因为我每次都在进行新的扫描（即启动程序的新实例，因为它所做的只是这次扫描），但也许它与内存分配有关？关于如何每次都进行快速运行的任何想法，或者为什么不能完成？其他程序（例如 SpaceMonger）设法在 10 秒内获得文件总数，即使我清除我的内存或在运行之间等待很长时间。所以，肯定有办法做到这一点，但不一定在 VB 中。

我可能自己写这个，但我试图完成它的具体方式让我失望。我正在尝试编写一种类似于 .NET 3.5 中引入的其他方法的通用扩展方法，它将采用嵌套的 IEnumerables（等等）并将其展平为一个 IEnumerable。有人有想法么？

具体来说，我在扩展方法本身的语法方面遇到了问题，因此我可以研究扁平化算法。

如今，似乎有不少主流语言支持函数文字。它们也被称为匿名函数，但我不在乎它们是否有名字。重要的是，函数文字是一个表达式，它产生一个尚未在其他地方定义的函数，例如在 C 中，&printf不计算在内。

编辑添加：如果你有一个真正的函数文字表达式<exp>，你应该能够将它传递给一个函数f(<exp>)或立即将它应用于一个参数，即。<exp>(5).

我很好奇哪些语言可以让你编写递归的函数文字。维基百科的“匿名递归”文章没有给出任何编程示例。

让我们以递归阶乘函数为例。

以下是我知道的：

• JavaScript / ECMAScript 可以做到这一点callee：

  /li>

• 在语言中很容易使用letrec，例如 Haskell（它叫它let）：

  let fac x = if x<2 then 1 else fac (x-1) * x in fac

  在 Lisp 和 Scheme 中有等价物。请注意， 的绑定fac是表达式的局部变量，因此整个表达式实际上是一个匿名函数。

还有其他人吗？

我在多年的编程中使用了很多递归来解决简单的问题，但我完全意识到有时由于内存/速度问题您需要迭代。

因此，在很久以前的某个时候，我去尝试查找是否存在将通用递归方法转换为迭代的任何“模式”或教科书方法，但一无所获。或者至少我记得没有任何帮助。

• 有一般规则吗？
• 有“模式”吗？

我一直在修补 BSP 树一段时间，也在玩线程。将三角形添加到 BSP 树时，就有机会创建一个新线程以并行处理数据。

上面的两个插入操作可以由两个线程执行，并且由于它们不会修改相同的数据，因此可以使用廉价的同步。

这种新方法尝试创建一个线程以并行完成操作，但如果无法创建线程也不应该失败（它将简单地恢复到原始算法）。

这是一种合理的编程习惯，还是我不正确地使用线程？我还没有找到任何关于这种技术的文献。我喜欢它倾向于充分利用我的 CPU（2 个内核），并且理论上可以扩展到任意数量的可用处理器。我不喜欢这可能会严重浪费 CPU 和内存。

我不得不多次这样做，通常是在尝试查找在哪些文件中使用了变量或函数时。

我记得过去使用 xargs 和 grep 来做到这一点，但我想知道是否有更简单的方法。

我在 SQL 服务器中有一个表，它具有 Item_ID、Item_ParentID 的正常树结构。假设我想迭代并获取特定 Item_ID 的所有 CHILDREN（在任何级别）。

递归似乎是解决这个问题的一个直观的候选者，我可以编写一个 SQL Server 函数来做到这一点。

如果我的表有很多记录，这会影响性能吗？如何避免递归并简单地查询表？请问有什么建议吗？

假设您有一个存储有序树层次结构的平面表：

这是一个图表，我们有[id] Name. 根节点 0 是虚构的。

您将使用什么简约方法将其作为正确排序、正确缩进的树输出到 HTML（或文本）？

进一步假设你只有基本的数据结构（数组和哈希图），没有带有父/子引用的花哨对象，没有 ORM，没有框架，只有你的两只手。该表表示为一个结果集，可以随机访问。

伪代码或纯英文都可以，这纯粹是一个概念问题。

额外的问题：有没有更好的方法在 RDBMS 中存储这样的树结构？

编辑和添加

回答一位评论者（Mark Bessey）的问题：根节点不是必需的，因为它永远不会被显示。ParentId = 0 是表达“这些是顶级”的约定。Order 列定义了如何对具有相同父节点的节点进行排序。

我所说的“结果集”可以被描绘成一个哈希图数组（保留在那个术语中）。因为我的例子本来就应该在那里。有些答案会加倍努力并首先构建它，但这没关系。

树可以任意深。每个节点可以有 N 个孩子。不过，我并没有完全想到“数百万个条目”树。

不要将我选择的节点命名（'Node 1.1.1'）误认为是可以依赖的东西。这些节点同样可以称为“Frank”或“Bob”，没有暗示命名结构，这只是为了使其可读。

我已经发布了我自己的解决方案，因此你们可以将其分解。

我一直在完成最近的计算机科学作业，涉及递归和大 O 表示法。我相信我非常了解这一点（当然，当然不完美！）但是有一个问题特别给我带来了最多的问题。奇怪的是，看着它，它看起来是作业中最简单的一个。

使用 big-Oh 表示法提供最佳增长率来解决以下递归？

T(1) = 2

T(n) = 2T(n - 1) + 1 对于 n>1

选择是：

• O(n log n)
• O(n^2)
• O(2^n)
• O(n^n)

我知道大 O 用作上限，用于描述该程序或进程将花费的最多计算量或最长运行时间。我觉得这个特定的递归应该是 O(n)，因为对于每个 n 值，递归最多只发生一次。由于 n 不可用，它要么比这更好，O(nlogn)，要么更糟，成为其他三个选项。

所以，我的问题是：为什么不是 O(n)？

我希望这种方法适用于任何给定数量的参数，我可以通过代码生成来做到这一点（有很多丑陋的代码），它可以通过递归来完成吗？如果是这样怎么办？我理解递归，但我不知道如何写这个。