clojure写多了,尾递归,lazy-seq构建的递归也就接触多了,但我一直很好奇,递归的效率与while,for相比那个更快,能不能给个测试例子,谢谢
理论上一样吧
尾递归如果没有优化,自然是比不上while
,for
的,因为存在栈的开销。
一般推荐用尾递归的语言里,都会做尾递归优化的吧,效率也就差不多了(瞎猜)
1 个赞
好像还真是这样,做LeetCode的完全平方数时,我用JS的代码:
let range = (start, end) => new Array(end - start).fill(start).map((el, i) => start + i);
function numSquares(num) {
var set = range(1,1 + Math.trunc(Math.sqrt(num))).map(x=>x*x);
iter = function iter(coll,step) {
if(coll.some(x=>x==0)) {
return step;
}else {
var res = [];
for(n1 of coll) {
for(n2 of set.filter(x=>x<= n1)) {
res.push(n1-n2);
}
}
return iter(res,step + 1);
}
}
return iter(set.map(x=> num - x),1);
}
测试用例
numSquare(13) //正常运行 2
numSquare(8935) //异常 给了我下面这个错误信息
在本地用nodejs编译没有这个问题,就是有点慢,如果把递归部分写在外面也是一样的
用clojure的话没有这种情况
(defn num-square [num]
(let [set (->> num
(Math/sqrt)
int
inc
(range 1)
(map #(* % %)))]
(loop [coll (map #(- num %) set)
step 1]
(if (some zero? coll)
step
(recur (for [n1 coll
n2 (filter #(<= % n1) set)]
(- n1 n2))
(inc step))))))
测试用例
(num-square 13) ;; 2
(num-square 8935) ;; 4