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

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

请评论这些功能之间的差异，如何在每次递归调用时在堆栈上需要多少内存。另外，您希望哪个版本更快，为什么？这两种球拍功能在速度/效率方面有什么区别？

谢谢！

来源

2013-10-18 dahui

他们都应该有几个步骤与y成比例。

第二个是一尾调用意思解释器可以做尾消除这意味着它占用堆栈上的恒定空间而在第一堆栈的大小正比于Y.

来源

2013-10-18 18:23:05 WorBlux

有没有必要包装它。 'racket'确实可以调用外部函数的优化。 – Sylwester

@Sylwester相关知识，编辑反映 – WorBlux

感谢您的回答 – dahui

myminus创建y延续到sub1递归评估的内容。这意味着您可以消耗球拍内存限制，从而使程序失败。在我的试验中，即使只有一千万个不会成功使用DrRacket中的标准128MB限制。

myminus_v2是tail recursive以来racket具有相同的属性，什么scheme要求，即尾调用将被优化到一个跳转，而不是成长的堆栈，y可以是任意大小，即只可用内存和处理能力是限制的大小。

您的程序是peano arithmetic的很好例子。

来源

2013-10-18 18:33:25 Sylwester

感谢您的回答！ – dahui

球拍支持深度递归，所以第一个不会得到一个特殊的“堆栈溢出”错误，它只会耗尽内存。用于实现延续的技术通常免费提供深度递归。 –

@RyanCulpepper你是对的。我已经多次看到它在所有内存中徘徊，从不堆栈溢出。更新。 – Sylwester

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

回答

相关问题