首頁 > Java > java教程 > 超越遞歸原語的函數的跳板?阿克曼彼得函數的實現

超越遞歸原語的函數的跳板?阿克曼彼得函數的實現

Barbara Streisand
發布: 2025-01-18 20:09:14
原創
174 人瀏覽過

Trampolim para funções além do primitivo recursivo? Implementação para a função de Ackermann Peter

在探索跳板技術時,我最初在更簡單的情況下使用它,只有一次遞歸——可能是原始遞歸函數的適當子集。 然而,在工作中需要執行非常長的計算。 我的第一個想法是 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 就會變成2 2 6553632^{2^{65536}} - 3

克服堆疊限制

問題在於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>
登入後複製
應用於Ackermann-Peter函數:此函數分為三種情況:基本情況、簡單遞歸和雙重遞歸。 跳板應該控制第二次遞歸的結果。 為此,第二個參數變成

。如果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) 下一步允許您推斷當前結果。 在解決第二個參數的延續之後應用記憶化。 提出了使用 HashMaplong 鍵(組合 mn)進行記憶的實現,證明了遞歸調用數量的顯著減少。 最終版本刪除了全域記憶體依賴,並傳遞 HashMap 作為參數。

以上是超越遞歸原語的函數的跳板?阿克曼彼得函數的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板