非尾递归的递归生成的数组参与运算会是lazy的吗？

flw

原帖由 MMMIX 于 2009-4-13 13:56 发表

表述不准确，没有“一些”。另外，如果你对这个存疑，可以试着构造一些不能变形为尾递归或者循环的递归的例子。

BTW，递归向循环的转换貌似是有数学证明的，可以翻翻计算理论方面的资料。

据说汉诺塔就是？

Magicloud

原帖由 MMMIX 于 2009-4-13 13:56 发表

表述不准确，没有“一些”。另外，如果你对这个存疑，可以试着构造一些不能变形为尾递归或者循环的递归的例子。

BTW，递归向循环的转换貌似是有数学证明的，可以翻翻计算理论方面的资料。

转换能为循环，运算也未必是lazy的，仍是前边说过的，如果编译器“认为”第一个元素依赖于其后的元素，那么取第一个就不是“理想”的lazy。
foldr不是尾递归的，但如何能测试出其运算过程是否lazy呢？

MMMIX

原帖由 flw 于 2009-4-13 14:02 发表

据说汉诺塔就是？

证明呢？

MMMIX

原帖由 Magicloud 于 2009-4-13 15:11 发表

转换能为循环，运算也未必是lazy的，仍是前边说过的，如果编译器“认为”第一个元素依赖于其后的元素，

你的意思是有些情况编译器无法优化？给出具体的例子，及它在理论上无法优化的原因。

win_hate

尾递归所需的空间是 O(1) 的，一般的递归不满足这个条件，比如 QuickSort.

梵塔的递归模式为  T(0)=0, T(n)=2T(n-1)+1

这个模式不是尾递归的，可以变形成尾递归或直接用迭代，但我觉得这个对编译器要求太高。

[ 本帖最后由 win_hate 于 2009-4-13 18:06 编辑 ]

Magicloud

原帖由 MMMIX 于 2009-4-13 17:05 发表

你的意思是有些情况编译器无法优化？给出具体的例子，及它在理论上无法优化的原因。

我就是想知道“理论证明，全部可以优化”，这样写代码就可以考虑更多的业务意义、易读性，而不是因为不能lazy而性能底下。

MMMIX

原帖由 Magicloud 于 2009-4-14 10:39 发表

我就是想知道“理论证明，全部可以优化”，这样写代码就可以考虑更多的业务意义、易读性，而不是因为不能lazy而性能底下。

你这个就属于过早优化了。写代码的时候你本来就应该更多考虑业务意义，写完以后，才是 profiling, 找出性能瓶颈以后才是优化。