use*_*571 4 algorithm recursion tail-recursion data-structures
我最近在学习日期结构.在Mark Allen Weiss的书中,C语言中的数据结构和算法分析,他为什么说尾递归是一种错误的递归使用,最好不要在第3章中使用它？但我看到很多人说它在网上很有用.
这不一定是坏事.尾递归总是等效于循环,显式写循环可能更有效,具体取决于编译器.(*)现代编译器(如GCC)可以优化尾递归,但它们并不总能识别它.当他们没有看到它时,递归将消耗堆栈空间.
也就是说,诸如quicksort之类的算法自然地递归地表达,并且其两个递归中的一个是尾递归.我会在第一次传递时递归写入它,然后如果我发现它太慢,则将其重写为循环.
当算法只有一个尾递归的递归时,将它立即写为循环可能仍然是一个好主意,因为递归函数比循环更难调试.
(*)我假设我们只谈论C.在其他一些语言中,尾递归可以被认为是循环的自然方式(函数语言)或彻底的憎恶(Python).