5

我想知道是否有一个非人为的例子，其中相互递归是解决问题的最优雅的解决方案，它不能轻易地减少/内联为单个递归函数。

我已经知道这个例子（来自维基百科）

function even?(number : Integer)
    if number == 0 then
        return true
    else
        return odd?(abs(number)-1)

function odd?(number : Integer)
    if number == 0 then
        return false
   else
        return even?(abs(number)-1)

但说真的，没有一个头脑正常的人会这样检查数字的奇偶性。

我在 SO 上查看了关于此主题的先前答案 -是否有任何相互递归的示例？但没有一个答案是我正在寻找的。

我知道它在递归解析中很有用——可能是实现它的唯一合乎逻辑的方式，但我需要一个更清晰、更具体的示例（最好是数学示例）。

谢谢你的帮助？

编辑：

由于显然每个相互递归函数的元组都可以简化为单个函数，所以我想知道是否存在使用相互递归函数是最好/最易读的方式的情况。

4

4 回答 4

5

用于绘制谢尔宾斯基曲线（和其他一些曲线）的相互递归代码看起来相当优雅。

于 2012-04-24T11:50:53.847 回答
4

我相信任何相互递归都可以很容易地简化为一个函数：

考虑两个函数 f1 和 f2：

f1(p1, ..., pn) returns r1
f2(q1, ..., qm) returns r2

可以统一为：

f12(which, p1, ..., pn, q1, ..., qn) returns (r1, r2)
    if which == 1
        <code of f1>
    else
        <code of f2>

这只是最坏的情况。通常一些参数或返回值应该是相同的。

于 2012-04-24T10:14:54.470 回答
2

一个人认为什么是“优雅”取决于个人的敏感性。但这是我的镜头。

Adam 正在尝试安排为期 6 天的考试复习。每天他都会：

  1. 休息 (R)
  2. 学习数学（M）
  3. 学习计算（C）

亚当从不连续两天学习两个不同的科目。亚当可以通过多少种方式安排他的修订？

解决方案：

让我们使用符号s1 = "RMCRMM"来表示时间表。s1不是一个有效的时间表，因为在时间表中的某一时刻，一个主题 (M) 紧跟在另一个主题 (C) 之后。一些有效时间表的例子是：s2 = "MMRCCR"或s3 = "MMRRRC"什至s4 = "RRRRRR"（祝你好运s4！）。在每个时间表中，两个不同的科目之间必须至少有一个休息日。

我们可以使用相互递归来解决这个任务。让我们列举从 开始的日子1, 2, ..., 6。让我们定义三个相互递归的函数，R(k)，M(k)，C(k)。每个函数将计算部分计划的数量，每个长度为k，其中最后几天分别是“R”、“M”和“C”。我们开始吧（python）：

def R(k):
    if k == 1:
        return 1
    else:
        return R(k-1) + M(k-1) + C(k-1)

def M(k):
    if k == 1:
        return 1
    else:
        return R(k-1) + M(k-1)

def C(k):
    if k == 1:
        return 1
    else:
        return R(k-1) + C(k-1)

然后我们可以通过评估来解决问题R(6) + M(6) + C(6)

这样做的原因是因为我们正在计算可能的方式来达到k几天的（部分）日程安排，这可能以给定的方式结束，唯一可能影响我们选择如何到达那里的事情是发生了什么在前一天。以这种方式，我们计算所有可能的时间表，并且我们只计算每个时间表一次。

例如，对于我们完成的第 3 天，比如在“C”、“XXC”，我们可以到达这样的时间表的方式数量正好是R(2) + C(2)，因为我们可能来自“XCC”或“XRC”时间表，但不是“XMC”。

显然，如果您想提高效率，您可能最终会使用记忆化/动态编程，但即便如此，相互递归也可能是编码问题的最易读/易理解的方式。

于 2018-02-14T09:41:07.117 回答
0

如果您有适当的尾调用优化，则可以进行协作多任务处理：

f():
    do_something()
    g()

g():
    do_something_else()
    f()

如果您碰巧在 Scheme 中编写代码，则有时需要考虑这一点。

于 2012-04-24T11:14:48.967 回答