1 
(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)))))

请根据每个递归调用在堆栈上需要多少内存来评论这些函数之间的差异。另外，您可能希望哪个版本更快，为什么？

谢谢！

4

2 回答 2

3

They should both have a number of steps proportional to y.

The second one is a tail call meaning the interpreter can do a tail elimination meaning it takes up a constant space on the stack whereas in the first the size of the stack is proportional to Y.

于 2013-10-18T18:23:05.483 回答
2

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

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

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

于 2013-10-18T18:33:25.507 回答