麦卡锡91功能如何工作

Question

我已经根据麦卡锡91以下功能原理：

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

当我在前奏 mc91 85我有 91键入

。

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

Answer 1

允许扩展代码：

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 

如果你看到recrusive电话，你会发现，一旦达到100或更高，在(mc91 101)调用结束它会降低它会带给我们最后91结果。

Answer 2

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

• 在这种情况下n > 100，那么我们返回n-10;并
• 在这种情况下n <= 100，那么我们计算n+11，我们做两个另外的步骤。

因而有两种可能的“台阶”：一个在那里我们有10递减，以及一个在那里我们有11递增，我们可以用图形可视化这一点，像：

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

我们注意到那是什么，这里有一个循环：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与任意数量的递归调用，我们将停止at 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