在探索跳板技術時,我最初在更簡單的情況下使用它,只有一次遞歸——可能是原始遞歸函數的適當子集。 然而,在工作中需要執行非常長的計算。 我的第一個想法是 busy beaver 函數,但是,除了計算複雜度高之外,我還不夠熟悉。 然後我選擇了一個更知名的函數:Ackermann-Peter 函數。
阿克曼-彼得函數
這是一個易於理解的函數,它接受兩個整數參數作為輸入:
<code class="language-java">int ackermannPeter(int m, int n) { if (m == 0) { return n + 1; } else if (n == 0) { return ackermannPeter(m - 1, 1); } return ackermannPeter(m - 1, ackermannPeter(m, n - 1)); }</code>
有關更多詳細信息,請參閱維基百科頁面或 WolframAlpha。
使用功能
測試ackermannPeter(3, 3)
時,結果計算正確。 然而,在執行ackermannPeter(4, 3)
時,發生了堆疊爆炸。 Ackermann-Peter函數的遞歸呼叫深度非常大;只要將第一個參數從3 改為4,輸出61 就會變成
克服堆疊限制
問題在於Ackermann-Peter函數的強烈遞歸,很快就耗盡了堆疊。 解決方案是使用延續來避免堆疊過載,實現跳板思想。在彈跳床上踏出一步需要三種行為:
<code class="language-java">interface Continuation { boolean finished(); int value(); Continuation step(); static Continuation found(int v) { /* ... */ } static Continuation goon(Supplier<Continuation> nextStep) { /* ... */ } }</code>
<code class="language-java">static int compute(Continuation c) { while (!c.finished()) { c = c.step(); } return c.value(); }</code>
。如果Continuation
已經完成,則該過程正常繼續;否則,在延續中採取一步,產生一個新的。 n
<code class="language-java">private static Continuation ackermannPeter(int m, Continuation c) { if (!c.finished()) { return Continuation.goon(() -> { final var next = c.step(); return Continuation.goon(() -> ackermannPeter(m, next)); }); } int n = c.value(); if (m == 0) { return Continuation.found(n + 1); } else if (n == 0) { return Continuation.goon(() -> ackermannPeter(m - 1, Continuation.found(1))); } return Continuation.goon(() -> ackermannPeter(m - 1, Continuation.goon(() -> ackermannPeter(m, Continuation.found(n - 1) ))) ); }</code>
新增記憶
記憶可以提高表現。 兩種情況:1)結果已經在記憶體中;2) 下一步允許您推斷當前結果。 在解決第二個參數的延續之後應用記憶化。 提出了使用 HashMap
和 long
鍵(組合 m
和 n
)進行記憶的實現,證明了遞歸調用數量的顯著減少。 最終版本刪除了全域記憶體依賴,並傳遞 HashMap
作為參數。
以上是超越遞歸原語的函數的跳板?阿克曼彼得函數的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!