マッカーシーの91関数は、私がマッカーシー91に基づいて機能を以下している

Question

の仕組み原則：

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

私は91を持っ前奏曲mc91 85に入力します。

私はそれを構成することができませんでした。どのように展開され、なぜ私は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通話が表示された場合、あなたはそれが私たちに最後の91をもたらす(mc91 101)コールで終わる、100以上を達成したら、それはそれを削減することを実現します結果。

Answer 2

最初に機能を分析しましょう。 2つのケースがあります。

場合 n > 100で

• 、その後、我々はn-10を返します。
• n <= 100の場合、n+11を計算し、を2つ追加します。追加の手順。

2の可能な「ステップ」これがあります。

：私たちは10でデクリメント1、私たちは11にインクリメント1は、我々は次のように、グラフでこれを可視化することができます第1のケースのエッジを黒で示し、後者のエッジを赤で示す。私たちは気づく何

は、ループがここにあるということです：92 -> 103 -> 93 -> 104 -> 94 -> 105 -> 95 -> 106 -> 96 -> 107 -> 97 -> 108 -> 98 -> 109 -> 99 -> 110 -> 100 -> 111 -> 101 -> 91 -> ...

は、今度はそのために仮定しよう - に関係なく、元の値の - 私たちは常にそのループになってしまいます。今度は、ループは常に黒い辺をインターリーブし、赤い辺は、111 -> 101 -> 91部分を除いて2つの黒い辺から構成されます。

赤いエッジは2つの追加の再帰呼び出しを導入するため、赤いホップを取ると次の黒と赤のホップが解放されます。次の赤いホップは再び「todoリスト」に2つの再帰呼び出しを追加します。その結果、ループを開始してから最初に赤いホップを取ると、ループを継続して実行します。これは、ループの一部である111 -> 101 -> 91を取らない限り保持されます。これらは2つの黒い辺であるため、再帰呼び出しを実行して実行することができ、したがって、91に停止することができます（これは、常に1つの赤いホップにつき2つのホップが追加されるためです）。

結果としてループ内の特定のノードから開始し、まだ実行する必要がある再帰呼び出しの数に関係なく、すぐに赤いホップをとると、最終的に91で停止します。 1つの再帰呼び出しを "失う"ため、結果的に残りの再帰呼び出しがなくなり、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