麥卡錫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