2

我有以下基于麦卡锡 91 原则的功能：

mc91 :: Integer -> Integer
mc91 n
    | n > 100 = n - 10
    | otherwise = mc91 (mc91 (n + 11))

mc91 85当我输入我得到的前奏曲时91。

我无法配置它，它是如何扩展的，为什么我有91.

4

2 回答 2

6

我们先来分析一下函数。有两种情况：

  • 在这种情况下n > 100，那么我们返回n-10；和
  • 在这种情况下n <= 100，然后我们计算n+11，并且我们执行两个额外的步骤。

因此有两个可能的“步骤”：一个是我们递减 10，一个是我们递增 11。我们可以用图表将其可视化，例如：

McCarthy91 函数的图形表示

第一种情况的边缘用黑色表示，后一种情况的边缘用红色表示。

我们注意到这里有一个循环：92 -> 103 -> 93 -> 104 -> 94 -> 105 -> 95 -> 106 -> 96 -> 107 -> 97 -> 108 -> 98 -> 109 -> 99 -> 110 -> 100 -> 111 -> 101 -> 91 -> ...

现在让我们假设——不管原始值如何——我们总是会进入那个循环。现在循环总是交错一个黑色边缘和一个红色边缘，除了111 -> 101 -> 91由两个黑色边缘组成的部分。

由于红色边缘引入了两个额外的递归调用，这意味着，如果我们采用红色跳跃，我们将免费获得下一个黑色和红色跳跃。下一个红色跃点将再次向“待办事项列表”添加两个递归调用。因此，如果我们从循环中开始，并且我们首先进行红色跳跃，我们将继续在循环中运行。只要我们不参与111 -> 101 -> 91循环，这就是成立的。由于那是两个黑边，我们可以摆脱递归调用来执行并因此停止91（因为我们总是在每个红色跃点获得两个额外的跃点）。

结果，如果我们从循环中的某个节点开始，我们立即进行一次红色跳，不管我们还需要做多少次递归调用，我们最终都会在 91 处停止：每次我们做一个完整的循环，我们“丢失”一个递归调用，所以最终我们将用完剩余的递归调用并在 91 处停止。所以现在我们知道，如果我们从94任意数量的递归调用开始，我们将在 91 处停止。

现在我们仍然需要证明 - 假设数字小于 100 - 我们将最终进入循环，并且我们在循环中遇到的第一个节点是红色边缘开始的节点。我们知道 91..100 范围内的所有数字都在循环中。任何小于 91 的数字都将导致红色跃点，并将增加 11。因此 - 正如图中部分所示 - 所有小于 91 的数字最终将在 [91..100] 范围内始终使用红色边缘。

基于上述推理，该函数的更有效版本将是：

mc91' n | n > 100 = n-10
        | otherwise = 91

现在对于您给定的示例输入（85），我们看到程序将评估为：

   mc91 85
-> mc91 (mc91 96) -- we are in the loop now
-> mc91 (mc91 (mc91 107))
-> mc91 (mc91 97)
-> mc91 (mc91 (mc91 108))
-> mc91 (mc91 98)
-> mc91 (mc91 (mc91 109))
-> mc91 (mc91 99)
-> mc91 (mc91 (mc91 110))
-> mc91 (mc91 100)
-> mc91 (mc91 (mc91 111))
-> mc91 (mc91 101)
-> mc91 91 -- we reached 91, and thus removed one recursive call
-> mc91 (mc91 102)
-> mc91 92
-> mc91 (mc91 103)
-> mc91 93
-> mc91 (mc91 104)
-> mc91 94
-> mc91 (mc91 105)
-> mc91 95
-> mc91 (mc91 106)
-> mc91 96
-> mc91 (mc91 107)
-> mc91 97
-> mc91 (mc91 108)
-> mc91 98
-> mc91 (mc91 109)
-> mc91 99
-> mc91 (mc91 110)
-> mc91 100
-> mc91 (mc91 111)
-> mc91 101
-> 91 -- we hit 91 a second time, and now the last recursive call is gone
于 2017-06-08T11:08:43.900 回答
4

让我们扩展您的代码：

mc91 85
mc91 (mc91 96)
mc91 (mc91 (mc91 107))
mc91 (mc91 97)
mc91 (mc91 (mc91 108))
mc91 (mc91 98)
mc91 (mc91 (mc91 109))
mc91 (mc91 99)
mc91 (mc91 (mc91 110))
mc91 (mc91 100)
mc91 (mc91 (mc91 111))
mc91 (mc91 101)
mc91 91... --It is a pattern here
...
mc91 101
91

如果你看到递归调用，你会意识到一旦达到 100 或更高，它就会减少它，最终(mc91 101)调用会为我们带来最后的91结果。

于 2017-06-08T10:00:00.690 回答