蹦床，Java 中的範例

讓我們寫一個簡單的程序，將從n到0的數字相加。但是，與其使用迭代方法，不如嘗試遞歸方法？

我們稱這個程式為sum。我們知道sum(0) == 0，所以這是我們的基本情況。我們如何到達基本情況？ sum(n) == n sum(n-1)，直到最終到達sum(0)。 Java程式碼如下：

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

遞迴問題？

遞歸在基本情況距離輸入值很遠時存在一個固有缺陷…在大多數語言中，函數呼叫使用程式的堆疊來儲存函數呼叫訊息，因此非常大的遞歸可能會導致堆疊溢位。

但是，有沒有辦法避免這種情況呢？實際上，有。這是一個古老的策略，稱為「彈簧跳板」（trampoline）。

彈簧跳板

彈簧跳板策略的基本想法是，程式的一部分回傳一個「值」或一個「延續」（continuation）。延續是什麼？一個將繼續處理的函數。

大致如下：

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum的延續是什麼？

讓我們將sum程式建模為：與其簡單遞歸，不如使用延續。一種方法是將acc作為一種透過延續傳遞的物件。因此，當到達sum_trampoline(0, acc)時，我們返回acc。如何進行下一步呢？

讓我們從sum_trampoline(n, acc)到sum_trampoline(n-1, acc n)。第一個輸入是sum_trampoline(n, 0)。

因此，程式碼如下：

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

使用型式描述彈簧跳板

彈簧跳板需要大致具有以下形式：

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

但這給了很大的編碼自由度，對於Java世界來說並不十分直觀。我們可以透過詢問對象來檢測是否為延續。如果我們詢問「是否已找到值」呢？另一件事是，由於Java沒有sum-types，return trampolim實際上會回傳trampolim類型，而不是傳回該值。我們可以回傳trampolim.value()。

最後，一個關鍵點是彈簧跳板的引導（bootstrapping）。為此，我們可以使用一個函數將輸入轉換為適當的彈簧跳板返回值。輸入和結果可以被泛化以更好地使用：

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

TrampolineStep<r></r>介面呢？

它定義了三個方法：

• gotValue：詢問是否已找到值
• value：傳回找到的值
• runNextStep：傳回一個值或一個延續

它基本上有兩個狀態：

• 已找到值
• 是一個延續

因此，我們可以使用靜態方法來初始化它。對於已找到值的情況，需要傳遞值：

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

對於延續的情況，需要傳遞如何取得延續的下一個項目：

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum_trampoline將如何實現？

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

尾調用斐波那契

斐波那契的經典實作遵循遞歸定義：

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

還有一個迭代版本，它非遞歸地展開斐波那契定義，而是向前推進：從0和1開始，直到達到對應的值：

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

這個實作有一個向前推進的版本，使用「尾呼叫遞歸」：

static <X> TrampolineStep<X> valueFound(X value) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return true;
        }

        @Override
        public X value() {
            return value;
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return this;
        }
    };
}

這裡我將輸入介面分離出來，它準備了將在尾呼叫遞歸斐波那契中使用的數。由於它向前推進，我們從映射fib[0] => 0, fib[1] => 1開始，從索引0開始導航，直到到達索引n。

斐波那契：從尾調用彈簧跳板

fib_tc的例子很好地說明了斐波那契的彈簧跳板：

static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return false;
        }

        @Override
        public X value() {
            throw new RuntimeException("dont call this");
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return x.get();
        }
    };
}

請注意，這只是一個骨架，需要完整的TrampolineStep介面實作以及trampoline函數的完整實作才能編譯和運行。 此外，IN 需要替換為特定的輸入類型。

以上是蹦床，Java 中的範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！