1 回答

TA貢獻(xiàn)1998條經(jīng)驗(yàn) 獲得超6個(gè)贊
與其使用loop/ recur(我認(rèn)為這是一種丑陋和不必要的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]
幾乎每個(gè)遞歸函數(shù)都可以使用折疊來定義(也稱為結(jié)構(gòu)遞歸,又稱為歸納)。例如,甚至可以使用折疊來定義Ackermann函數(shù):
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秒才能在筆記本電腦上計(jì)算出答案。
現(xiàn)在,您可能會問為什么我recNat使用迭代而不是自然遞歸來實(shí)現(xiàn):
const recNat = (zero, succ) => function recNatZS(n) {
return n <= 0 ? zero : succ(recNatZS(n - 1));
};
我使用迭代的原因與您使用迭代實(shí)現(xiàn)的原因相同loop。踩踏。通過為要折疊的每種數(shù)據(jù)類型實(shí)現(xiàn)不同的蹦床,您可以編寫功能代碼,而不必?fù)?dān)心堆棧溢出。
底線:使用折疊而不是顯式遞歸。它們比您想像的強(qiáng)大得多。
添加回答
舉報(bào)