这两种球拍功能在速度/效率方面有什么区别

Question

(define (myminus x y)
  (cond ((zero? y) x)
        (else (sub1 (myminus x (sub1 y))))))
(define (myminus_v2 x y)
  (cond ((zero? y) x)
        (else (myminus_v2 (sub1 x) (sub1 y)))))

请评论这些功能之间的差异每个递归调用的堆栈上都需要大量内存。另外，哪个版本可能你希望更快，为什么？

谢谢！

Answer 1

它们都应该具有与 y 成比例的步长数。

第二个是尾部调用，这意味着

解释器可以执行尾部消除，这意味着它在堆栈上占用恒定的空间，而在第一个中，堆栈的大小与 Y 成正比。

Answer 2

myminus创建y延续来sub1递归的计算结果。这意味着您可以耗尽球拍内存限制，使程序失败。在我的试验中，即使是只有1000万也不会成功达到DrRacket的标准128MB限制。

myminus_v2是tail recursive的，并且由于racket具有与scheme所需的属性相同的属性，因此尾部调用将优化为goto而不是增加堆栈，因此y可以是任何大小，即只有可用的内存和处理能力是大小的限制。

你的程序是皮亚诺算术的很好的例子。