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

我們將這個(gè)程序稱為sum。我們知道sum(0) == 0，所以這是我們的基本情況。我們?nèi)绾蔚竭_(dá)基本情況呢？sum(n) == n sum(n-1)，直到最終到達(dá)sum(0)。Java代碼如下：

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

遞歸問題？

遞歸在基本情況距離輸入值很遠(yuǎn)時(shí)存在一個(gè)固有缺陷……在大多數(shù)語言中，函數(shù)調(diào)用使用程序的堆棧來存儲函數(shù)調(diào)用信息，因此非常大的遞歸可能會導(dǎo)致堆棧溢出。

但是，有沒有辦法避免這種情況呢？實(shí)際上，有。這是一個(gè)古老的策略，稱為“彈簧跳板”（trampoline）。

彈簧跳板

彈簧跳板策略的基本思想是，程序的一部分返回一個(gè)“值”或一個(gè)“延續(xù)”（continuation）。延續(xù)是什么？一個(gè)將繼續(xù)處理的函數(shù)。

大致如下：

let trampolim = primeiraChamada(input);

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

sum的延續(xù)是什么？

讓我們將sum程序建模為：與其簡單地遞歸，不如使用延續(xù)。一種方法是將acc作為一種通過延續(xù)傳遞的對象。因此，當(dāng)?shù)竭_(dá)sum_trampoline(0, acc)時(shí)，我們返回acc。如何進(jìn)行下一步呢？

讓我們從sum_trampoline(n, acc)到sum_trampoline(n-1, acc n)。第一個(gè)輸入是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世界來說并不十分直觀。我們可以通過詢問對象來檢測是否為延續(xù)。如果我們詢問“是否已找到值”呢？另一件事是，由于Java沒有sum-types，return trampolim實(shí)際上會返回trampolim類型，而不是返回該值。我們可以返回trampolim.value()。

最后，一個(gè)關(guān)鍵點(diǎn)是彈簧跳板的引導(dǎo)（bootstrapping）。為此，我們可以使用一個(gè)函數(shù)將輸入轉(zhuǎn)換為適當(dāng)?shù)膹椈商宸祷刂?。輸入和結(jié)果可以被泛化以更好地使用：

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>接口呢？

它定義了三個(gè)方法：

• gotValue：詢問是否已找到值
• value：返回找到的值
• runNextStep：返回一個(gè)值或一個(gè)延續(xù)

它基本上有兩個(gè)狀態(tài)：

• 已找到值
• 是一個(gè)延續(xù)

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

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

對于延續(xù)的情況，需要傳遞如何獲取延續(xù)的下一個(gè)項(xiàng)目：

let trampolim = primeiraChamada(input);

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

sum_trampoline將如何實(shí)現(xiàn)？

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);
}

尾調(diào)用斐波那契

斐波那契的經(jīng)典實(shí)現(xiàn)遵循遞歸定義：

let trampolim = primeiraChamada(input);

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

還有一個(gè)迭代版本，它非遞歸地展開斐波那契定義，而是向前推進(jìn)：從0和1開始，直到達(dá)到相應(yīng)的值：

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();
}

這個(gè)實(shí)現(xiàn)有一個(gè)向前推進(jìn)的版本，使用“尾調(diào)用遞歸”：

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;
        }
    };
}

這里我將輸入接口分離出來，它準(zhǔn)備了將在尾調(diào)用遞歸斐波那契中使用的數(shù)。由于它向前推進(jìn)，我們從映射fib[0] => 0, fib[1] => 1開始，從索引0開始導(dǎo)航，直到到達(dá)索引n。

斐波那契：從尾調(diào)用到彈簧跳板

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();
        }
    };
}

請注意，這只是一個(gè)骨架，需要完整的TrampolineStep接口實(shí)現(xiàn)以及trampoline函數(shù)的完整實(shí)現(xiàn)才能編譯和運(yùn)行。 此外，IN 需要替換為具體的輸入類型。

以上是蹦床，Java 中的示例的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！