问题标签 [mutual-recursion]

卢恩算法

用于验证信用卡号码

1. 从最右边的数字（即校验位）开始，向左移动，每第二位的值加倍；如果这个加倍运算的乘积大于 9（例如，8 × 2 = 16），则将乘积的数字相加（例如，16: 1 + 6 = 7, 18: 1 + 8 = 9）或减法9 来自产品（例如，16：16 - 9 = 7、18：18 - 9 = 9）。
2. 取所有数字的总和。
3. 如果总模 10 等于 0（如果总和以 0 结尾），那么根据 Luhn 公式，该数是有效的；否则无效。

执行

如何分析相互递归代码的空间和时间复杂度？

我尝试使用归纳数据类型的语法，但它收到一条错误消息“相互归纳类型必须编译为具有依赖消除的基本归纳类型”。

下面是我尝试定义命题even和odd自然数的示例

还有一个相关的问题：定义相互递归函数的语法是什么？我似乎无法在任何地方找到它的记录。

我编写了以下函数来检查括号表达式的有效性：

如果我们替换matchClosinginto的实现matched'，我们会得到一个尾递归函数。F# 编译器可以识别这一点并优化递归调用吗？

这是我一直在研究的第二个 SML 程序。这些函数是相互递归的。如果我调用奇数（1）我应该得到真，偶数（1）我应该得到假。这些函数应该适用于所有正整数。但是，当我运行这个程序时：

我得到：

我怎样才能解决这个问题？

在某些编程语言中，尤其是在 C 语言中，有带有函数声明的头文件。这些函数“标头”位于代码之前，在相互递归的情况下是必需的。将函数头放在头文件中时，它们还有助于链接多个 C 文件一起编译的情况。

我对 C 文件中的函数头的理解是它们有助于编译，因为它们定义了函数的类型（如果在定义之前调用它）。如果这是错误的，我很乐意接受纠正和更好的了解，但这是我对它的理解。

所以我不明白的是，为什么其他语言——在这种情况下我选择 OCaml——没有函数头。在 OCaml 中，有带有签名的模块，但签名不允许您的函数实例相互递归，即使给出了类型。为了在 OCaml 中实现相互递归，您需要使用“and”关键字，或者在另一个函数中本地定义一个函数（据我所知）。

那么为什么会这样呢？它与多态性有关吗？是否存在我没​​有考虑的编译瓶颈？

我目前正在开发一个模块，该模块允许用户通过创建任务对象的实例（我的模块提供一个任务类）来构建任意任务网络模型（用于离散事件模拟）。除其他外，任务包含描述其完成效果的逻辑，例如不同任务的启动。这样，任务类的一个实例可以引用一个或多个其他实例，具有循环引用/相互递归的可能性。

这是我的代码的一个极其简化的版本：

任务模块.py

任务测试.py

这个实现的问题是我在定义 task2 和 task3 之前就引用了它们。如果我可以排除循环引用，那将不会是世界末日——这只是重新安排对象实例化顺序的问题——但我相信我应该适应这种可能性。我已经考虑了几个潜在的解决方法——大多数会涉及要求用户间接引用任务（即通过一些唯一的标识符值）——但我想知道是否有一个更优雅的解决方案，它涉及一种巧妙的抽象形式。

确保实例化任务/生成任务网络的过程（如 TaskTest.py 中所示）尽可能简单易行是该项目的首要任务，因为这是我模块的用户将花费的大部分时间时间做。

我尝试搜索，但似乎大多数关于相互递归/循环引用主题的问题都涉及函数或类而不是实例。

该mergeSort算法是否使用相互递归？我意识到mergeSort调用merge函数并且它调用自身（mergeSort），但是由于merge不调用mergeSort它不是相互递归而只是递归吗？

考虑以下无类型 lambda 演算的玩具表示：

类型检查print失败并出现以下错误：

什么是最易读/符合人体工程学/最有效的实现方式？

我开始学习球拍，我正在使用任意数量树和生成递归从给定的板上获取板的每个可能版本。

所以假设我有这个板，其中 false 表示为空：

根据要求，解决方案是：

球拍中的解决方案效果很好。我在 Python 中尝试了同样的事情，但它并没有像预期的那样工作。

我不断得到这样的输出：

或者

或更糟。

我似乎无法让它给我想要的输出。

如果没有其他方法，我正在考虑对输出进行一些后期处理，但我想避免这种情况。

我需要的是这个：

无论如何，让我知道您是否可以提供帮助。

这是我的python代码：

如果我编写以下代码，JSLint 会抱怨在定义之前使用了 'isOdd'。有没有办法编写相互递归的代码并且仍然取悦 JSLint？