1 回答

TA貢獻1998條經驗 獲得超6個贊
與其使用loop/ recur(我認為這是一種丑陋和不必要的hack),不如考慮使用folds:
const recNat = (zero, succ) => n => {
let result = zero;
while (n > 0) {
result = succ(result);
n = n - 1;
}
return result;
};
const mul = x => y => x * y;
const pow = x => recNat(1, mul(x));
console.log([0,1,2,3,4,5,6,1e6].map(pow(2))); // [1,2,4,8,16,32,64,Infinity]
幾乎每個遞歸函數都可以使用折疊來定義(也稱為結構遞歸,又稱為歸納)。例如,甚至可以使用折疊來定義Ackermann函數:
const recNat = (zero, succ) => n => {
let result = zero;
while (n > 0) {
result = succ(result);
n = n - 1;
}
return result;
};
const add = x => y => x + y;
const ack = recNat(add(1),
ackPredM => recNat(ackPredM(1),
ackMPredN => ackPredM(ackMPredN)));
console.time("ack(4)(1)");
console.log(ack(4)(1)); // 65533
console.timeEnd("ack(4)(1)");
上面的代碼段大約需要18秒才能在筆記本電腦上計算出答案。
現在,您可能會問為什么我recNat使用迭代而不是自然遞歸來實現:
const recNat = (zero, succ) => function recNatZS(n) {
return n <= 0 ? zero : succ(recNatZS(n - 1));
};
我使用迭代的原因與您使用迭代實現的原因相同loop。踩踏。通過為要折疊的每種數據類型實現不同的蹦床,您可以編寫功能代碼,而不必擔心堆棧溢出。
底線:使用折疊而不是顯式遞歸。它們比您想像的強大得多。
添加回答
舉報