以前我很少寫遞回，因為感覺寫遞回需要靈感，很難復制，看了《The Little Schemer》后，我發現寫遞回其實是有套路的，遞回只需要想清楚 2 個問題：
- 什么情況不需要計算
- 大問題怎么變成小問題
舉例
1. 判斷陣列是否包含某元素
const has = (element, arr) => {};
-
什么情況不需要計算？
陣列為空時不需要計算，一定不包含，const has = (element, arr) => { if (arr.length === 0) return false; }; -
怎么把大問題變成小問題？
把arr的長度減小，向陣列為空的情況逼近，
從arr中取出第一個元素和element比較：- 相同：回傳
true， - 不相同：求解更小的問題，
const has = (element, arr) => { if (arr.length === 0) return false; else if (arr[0] === element) return true; else return has(element, arr.slice(1)); }; - 相同：回傳
2. 洗掉陣列的某個元素
const del = (element, arr) => {};
-
什么情況不需要計算？
陣列為空時不需要計算，回傳空陣列，const del = (element, arr) => { if (arr.length === 0) return []; }; -
怎么把大問題變成小問題？
把arr的長度減小，向空陣列的情況逼近，
從arr中取出第一個元素和element比較：- 相同：回傳陣列余下元素，
- 不相同：留下該元素，再求解更小的問題，
const del = (element, arr) => { if (arr.length === 0) return []; else if (arr[0] === element) return arr.slice(1); else return [ arr[0], ...del(element, arr.slice(1)) ]; };
3. 階乘、斐波那契
階乘、斐波那契用遞回來寫也是這個套路，代碼結構都是一樣的，
先列出不需要計算的情況，再寫大問題和小問題的轉換關系，
const factorial = n => {
if (n === 1) return 1;
else return n * factorial(n - 1);
};
const fibonacci = n => {
if (n === 1) return 1;
else if (n === 2) return 1;
else return fibonacci(n - 1) + fibonacci(n - 2);
};
4. 小孩子的加法
小孩子用數數的方式做加法，程序是這樣的：
3 顆糖 加 2 顆糖 是幾顆糖？
小孩子會把 3 顆糖放左邊，2 顆糖放右邊，
從右邊拿 1 顆糖到左邊，數 4，
再從右邊拿 1 顆糖到左邊，數 5，
這時候右邊沒了，得出有 5 顆糖，
這也是遞回的思路，
const add = (m, n) => {};
-
當
n = 0時，不需要計算，結果就是m，const add = (m, n) => { if (n === 0) return m; }; -
把問題向
n = 0逼近：const add = (m, n) => { if (n === 0) return m; else return add(m + 1, n - 1); };
當然
m = 0也是不需要計算的情況，
選擇m = 0還是n = 0作為不需要計算的情況 決定了 大問題轉成小問題的方向，
Continuation Passing Style
const add1 = m => m + 1;
把 add1 的回傳結果乘 2，通常這么寫：
add1(5) * 2;
用 Continuation Passing Style 來實作是這樣的：
const add1 = (m, continuation) =>
continuation(m + 1);
add1(5, x => x * 2);
add1 加一個引數 continuation，它是一個函式，表示對結果的后續操作，
我們用 Continuation Passing Style 來寫寫遞回，
以下用
CPS代替Continuation Passing Stylecont代替continuation
1. 階乘
const factorial = (n, cont) => {
if (n === 1) return cont(1);
else return factorial(n - 1, x => cont(n * x));
};
- 如果
n === 1，把結果1交給cont； - 如果
n > 1，計算n - 1的階乘，
把n - 1階乘的結果x乘n，交給cont，
這個
factorial函式該怎么呼叫呢？
cont可以傳x => x，這個函式傳入什么就回傳什么，factorial(5, x => x);
-
之前的寫法：
const factorial = n => { if (n === 1) return 1; else return n * factorial(n - 1); };遞回呼叫
factorial不是函式的最后一步，還需要乘n，
因此編譯器必須保留堆疊， -
新寫法：
const factorial = (n, cont) => { if (n === 1) return cont(1); else return factorial(n - 1, x => cont(n * x)); };遞回呼叫
factorial是函式的最后一步，
做了尾遞回優化的編譯器將不保留堆疊，從而不怕堆疊深度的限制，
也就是說：可以通過 CPS 把遞回變成尾遞回，
2. 斐波那契
const fibonacci = (n, cont) => {
if (n === 1) return cont(1);
else if (n === 2) return cont(1);
else
return fibonacci(n - 1, x =>
fibonacci(n - 2, y => cont(x + y))
);
};
- 如果
n === 1，把結果1交給cont； - 如果
n === 2，把結果1交給cont； - 如果
n > 2，
計算n - 1的結果x，
計算n - 2的結果y，
把x + y交給cont，
3. CPS 尾遞回使用誤區
-
cont傳入的引數不是最終結果，CPS中cont是對結果的后續操作，
也就是說cont傳入的引數需要是最終結果，
不滿足這一點，就不能叫做CPS，錯誤代碼示例：
const factorial = (n, cont) => { if (n === 1) return cont(1); else return factorial(n - 1, x => cont(n) * x); };上述代碼和之前代碼的區別如下：
x => cont(n) * x; // 現在 錯誤的寫法 x => cont(n * x); // 之前 正確的寫法錯誤的寫法中，
cont傳入的引數不再是最終結果了，如果這么呼叫：factorial(5, console.log);期望控制臺列印
120，
實際控制臺列印5， -
是
CPS，卻不是尾遞回，const factorial = (n, cont) => { if (n === 1) return cont(1); else return cont(factorial(n - 1, x => n * x)); };以上寫法稱得上是
CPS了，但卻不是尾遞回，注意這段代碼：
cont(factorial(n - 1, x => n * x));factorial的遞回呼叫不是函式的最后一步，cont的呼叫才是最后一步，
4. 驗證 CPS 尾遞回優化
截止到 2019 年 11 月，只有 Safari 瀏覽器宣稱支持尾遞回優化，
用從 1 加到 N 的例子試驗了一下，Safari 13.0.3：
-
一般遞回：堆疊溢位，
"use strict"; const sum = n => { if (n === 1) return 1; else return n + sum(n - 1); }; sum(100000); -
CPS尾遞回：正常算出結果，"use strict"; const sum = (n, cont) => { if (n === 1) return cont(1); else return sum(n - 1, x => cont(n + x)); }; sum(1000000, x => x);
最后想說的
用以前的方式寫遞回 還是 用 CPS 寫遞回，只是寫法上不同，思想都是一樣的，都是要搞清：
- 什么情況不需要計算
- 大問題怎么變成小問題
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/169443.html
標籤：JavaScript