[编程疑问]尾递归与while,for的效率相比如何

闲聊灌水
1

clojure写多了,尾递归,lazy-seq构建的递归也就接触多了,但我一直很好奇,递归的效率与while,for相比那个更快,能不能给个测试例子,谢谢 :grin:

2

理论上一样吧

3

尾递归如果没有优化，自然是比不上while,for的，因为存在栈的开销。

4

一般推荐用尾递归的语言里，都会做尾递归优化的吧，效率也就差不多了（瞎猜）

1 个赞
5

Emacs Lisp没有实现这方面的优化，来自 https://www.iro.umontreal.ca/~monnier/hopl-4-emacs-lisp.pdf

image
image862×308 46.2 KB

4 个赞
6

好像还真是这样，做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) //异常 给了我下面这个错误信息

2020-05-22 17-01-41 的屏幕截图
2020-05-22 17-01-41 的屏幕截图1355×661 72.4 KB

在本地用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