考慮一個函式 g(x)：
g(x) = x == 0 ? 0 : g(g(x - 1))
我不認為這是尾遞回，因為對 g(x) 的呼叫可以分為兩部分：
let y = g(x - 1);
return g(y);
如何將其轉換為尾遞回？
uj5u.com熱心網友回復：
續傳風格
您可以從直接風格轉換為延續傳遞風格-
g'(x,return) =
x == 0
? return(0)
: g'(x - 1, x' => # tail
g'(x', return)) # tail
現在用默認的延續寫g來呼叫g'-
g(x) = g'(x, x' => x')
根據您使用的語言，您可能需要重命名return為其他名稱。k是一個受歡迎的選擇。
另一個例子
我們可以看到這種技術應用于其他問題，例如fib-
# direct style
fib(x) =
x < 2
? x
: fib(x - 1) fib(x - 2) # " " has tail position; not fib
# continuation-passing style
fib'(x, return) =
x < 2
? return(x)
: fib'(x - 1, x' => # tail| first compute x - 1
fib(x - 2, x'' => # tail| then compute x - 2
return(x' x''))) # tail| then return sum
fib(x) = fib'(x, z => z)
其他用途
延續傳遞風格在其他方面也很有用。例如，它可用于在此search程式中提供分支或提前退出行為-
search(t, index, match, ifFound, notFound) =
i >= length(t)
? notFound()
: t[index] == match
? ifFound(index)
: search(t, index 1, match, ifFound, notFound)
我們可以search為每個可能的結果呼叫continuation -
search(["bird", "cat", "dog"],
0,
"cat",
matchedIndex => print("found at: " matchedIndex),
() => print("not found")
)
如何
以延續傳遞風格撰寫的函式需要一個額外的引數：一個顯式的“延續”；即，一個引數的函式-維基百科
(* direct style *)
add(a, b) = ...
(* continuation-passing style takes extra argument *)
add(a, b, k) = ...
當 CPS 函式計算出它的結果值時，它會通過以該值作為引數呼叫延續函式來“回傳”它。
(* direct style *)
add(a, b) =
a b
(* continuation-passing style "returns" by calling continuation *)
add(a, b, k) =
k(a b) (* call k with the return value *)
這意味著在呼叫 CPS 函式時，呼叫函式需要提供要使用子例程的“回傳”值呼叫的程序。
(* direct style *)
print(add(5, 3)) (* 8 *)
(* continuation-passing style *)
add(5, 3, print) (* 8 *)
以這種形式表達代碼使許多事情變得明確，而這些事情在直接風格中是隱含的。其中包括： 程序回傳，作為對延續的呼叫變得明顯；中間值，它們都是給定的名稱；引數評估的順序，這是明確的；和尾呼叫，它簡單地呼叫具有相同延續的程序，未修改，傳遞給呼叫者。
你以前可能用過延續
如果您曾經遇到過有人說“回呼”，那么他們真正的意思是繼續。
“當按鈕被點擊時，繼續程式event => ...” -
document.querySelector("#foo").addEventListener("click", event => {
console.log("this code runs inside a continuation!")
})<button id="foo">click me</button>“讀取檔案內容后，繼續執行程式(err, data) => ...” -
import { readFile } from 'fs';
readFile('/etc/passwd', (err, data) => {
if (err) throw err;
console.log(data);
});
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/417798.html
標籤：
上一篇：如何從BinaryTree列印出具有連續編號的節點值？
下一篇：c#如何在所有目錄中搜索檔案？