问题标签 [recursion]

我正在为我的一个练习项目实现一个树标记，我将在其中以树的形式（递归）显示目录的内容。在 JSP2.0 之前的日子里，我已经实现了与 Java 中的自定义标记类似的要求。处理目录需要递归（处理子目录）！是否可以将其编码为标记文件并且可以以递归方式使用它们？

这是一个脑筋急转弯的问题，因为代码按原样工作得非常好，它只是稍微刺激了我的审美意识。我转向 Stack Overflow 是因为我自己的大脑现在让我失望了。

这是一段使用 Google Maps JS API 查找地址并在地图上放置标记的代码片段。但是，有时初始查找会失败，所以我想用不同的地址重复这个过程。

（第二个参数getLatLng是回调函数。）

当然，您可以看到使地图居中和缩放地图以及添加标记的三行是重复的，一次在主回调中，一次在“后备回调”中（哈哈）。你能找到一种方法来表达整个事情而没有任何冗余吗？如果您的解决方案适用于任意数量的备份地图字符串，您将获得奖励积分和我的赞美。

如果我创建列表的递归列表：

然后稍后调用 tempList.Clear()，它会破坏内存中的所有 childList，还是我应该创建一个递归方法先清除所有 childList？

很简单，什么是尾调用优化？

更具体地说，有哪些小代码片段可以应用，哪些不可以，并解释原因？

我目前正在将 SQL Server SQL 语句翻译成它们的 ANSI 通用等效语句，并且我坚持使用 WITH 语句的递归语句。

为了集中讨论这个问题，我将问题简化如下

如果我有两张桌子

1. 报告单位

   • col1：键
   • col2: ParentReportingUnitKey

2. 设施

   • col1：键
   • col2: ParentReportingUnitKey

此结构描述了向下至设施的报告单位的层次结构，其中报告单位可能有 0 .. 1 个直接父报告单位和 0 .. n 个子报告单位。

设施是链接到报告单位的“叶”记录。

我需要制作一个 ANSI 92 有效的 SQL 语句（或者最坏的情况下可以在 Oracle、DB2 和 SQL Server 上工作的语句），它将返回与层次结构中任何位置的给定报告单元相关的所有设施。

例如

• ReportingUnit R1 具有 ReportingUnit 子 R1.1 和 R1.2
• ReportingUnit R1.1 有子 R1.1.1、R1.1.2

• ReportingUnit R1.2 有子 R1.2.1、R1.2.2

• 设施 F1 有一个父报告单元 R1.1.1

• 设施 F2 有一个父报告单元 R1.1.2
• 设施 F3 有一个父报告单元 R1.2.1
• 设施 F4 有一个父报告单元 R1.2.2

请记住，ReportingUnit 表中可能有 0 .. n 级递归，如果给定参数 ReportingUnit=R1，我如何从 SQL 语句中返回所有 4 个工具？

出于某种原因，我很难想出一种重写此函数的好方法，以便它使用恒定的堆栈空间。大多数关于树递归的在线讨论都是通过使用斐波那契函数并利用该特定问题的属性来作弊的。有没有人对递归的这种“真实世界”（嗯，比斐波那契数列更真实）使用有任何想法？

Clojure是一个有趣的案例，因为它没有尾调用优化，而只有通过“recur”特殊形式的尾递归。它还强烈反对使用可变状态。它确实有许多惰性结构，包括tree-seq，但我看不到它们如何帮助我解决这种情况。谁能分享他们从 C、Scheme、Haskell 或其他编程语言中学到的一些技术？

编辑：根据评论中的要求...

用一般术语重述并使用 Scheme——如何重写以下递归模式，使其不消耗堆栈空间或需要对非自调用进行尾调用优化？

我选择了烦人的名字来说明我正在寻找不依赖于 x、浸渍、frobnicate、f、g 或 h 的代数属性的答案。我只想重写递归。

更新：

Rich Hickey为 Clojure添加了一个显式的蹦床函数。

我在我的项目中使用（GNU）Make。我目前正在为每个目录放置一个 makefile，并使用 SUBDIRS 指定子目录。有人向我建议，这不是使用 make 的理想方式，而是使用一个顶级 make 文件（或多个，使用 include 拆分）。我过去曾尝试过迁移/使用此布局，但在我看来，它没有必要复杂。

使用递归 makefile 有哪些优点/缺点？

我正在尝试使用 Suckerfish css 菜单和 Jquery 从表中创建菜单。我使用这个作为我的参考：Suckerfish menu with ASP.NET and JQuery，我让它使用手动提供的链接（很像文章中的）。

我遇到问题的地方是编写递归函数以从数据库中获取菜单项并在适当的层次结构中创建新的菜单项。我的数据库表如下所示：

表菜单

MenuID ParentID 链接文本

这个想法是，如果一个项目是父级项目，则 MenuID 和 ParentID 是相同的，如果它是一个孩子，它将在 ParentID 字段中具有它的父级的 MenuID。我需要创建一个函数，可以通过并找到父母的所有孩子（可能是几个级别），并让它替换像这样的手动输入：

如有必要，我愿意更改数据库表结构，并且基本上会做任何其他事情来实现这一点。

感谢您的任何意见，非常感谢。

我编写了一个实验性的函数评估器，它允许我将简单的函数绑定在一起，这样当变量发生变化时，依赖于这些变量的所有函数（以及依赖于这些函数的函数等）都会同时更新。我这样做的方式不是在输入函数时立即评估函数，而是存储函数。仅当请求输出值时，我才评估函数，并且每次请求输出值时都对其进行评估。

例如：

我将“pi”和“rad”定义为变量（嗯，返回常量的函数），将“area”和“perim”定义为函数。每当“pi”或“rad”发生变化时，我都希望“area”和“perim”的结果会发生变化。同样，如果有任何函数依赖于“区域”或“周边”，那么它们的结果也会发生变化。

这一切都按预期工作。这里的问题是当用户引入递归时——无论是偶然的还是有意的。我的语法中没有逻辑——它只是一个评估器——所以我不能为用户提供一种“突破”递归的方法。我想完全阻止它发生，这意味着我需要一种方法来检测它并将有问题的输入声明为无效。

例如：

现在评估最后一行会导致 StackOverflowException（而前两行评估为 '0' - 未声明的变量/函数等于 0）。我想做的是检测循环逻辑情况并禁止用户输入这样的语句。无论循环逻辑隐藏多深，我都想这样做，但我不知道如何去做。

顺便说一句，在幕后，输入字符串通过简单的扫描器转换为标记，然后通过手写递归下降解析器转换为抽象语法树，然后评估 AST。语言是 C#，但我不是在寻找代码解决方案 - 仅逻辑就可以了。

注意：这是我用来了解解析器和编译器如何工作的个人项目，因此它不是关键任务 - 但是我从中获得的知识我确实计划在某些时候投入到现实生活中。你们可以提供的任何帮助将不胜感激。=)

编辑：如果有人好奇，我博客上的这篇文章描述了我为什么要学习这个，以及我从中得到了什么。

我有一个包含站点地图层次结构的 DataTable，其中包含以下列：

• 项目 ID
• 父 ID
• 姓名
• 网址

我需要在 HTML 中生成一组嵌套列表（为了清楚起见，将锚元素留在了外面）：

树应该只包含通向“当前”节点/页面的分支（因此使用上面的示例，项目“1”或“3”所具有的任何子项都不会显示。任何人都可以帮助提供一些伪代码/代码示例可以遍历树从叶子到根构建HTML吗？谢谢。