递归版本的“find”与不递归版本之间有什么区别？

在书中加速C++编程，205页上，有以下两个实施find递归版本的“find”与不递归版本之间有什么区别？

template <class In, class X> In find(In begin, In end, const X& x)

我想知道是什么在性能方面有什么区别（不管实际上是相同的后编译？）以下两种实现。

非递归

template <class In, class X> In find(In begin, In end, const X& x) 
{ 
    while (begin != end && *begin != x) 
     ++begin; 
    return begin; 
}

递归

template <class In, class X> In find(In begin, In end, const X& x) 
{ 
    if (begin == end || *begin == x) 
     return begin; 
    begin++; 
    return find(begin, end, x); 
}

通过使用编译器Explorer中建议通过Kerrek我得到了以下

非递归https://godbolt.org/g/waKUF2

递归https://godbolt.org/g/VKNnYZ

编译后好像完全一样？（如果我正确使用工具..对不起，我对C++非常陌生）

来源

2017-01-08 Yuhao Tiger Huang

你为什么不试试两者，并告诉我们你发现了什么？ –

尾递归可以导致很好的，干净的解决方案，但是您最好希望编译器将其优化为循环而不是递归（如果传递必要的优化标志，几乎所有编译器都会这样做，但如果优化可能不会关闭（如在调试版本中））。否则，如果搜索一个长列表，可能会导致堆栈溢出。 – Cornstalks

[示例]（https://godbolt.org/g/Ql4X3d） –

递归函数将添加在堆栈上额外元件。这可能会导致堆栈溢出错误，具体取决于启动递归之前堆栈的状态以及递归次数。

每个函数调用都会将数据压入包含返回地址的堆栈中。这一直持续到找到数据。此时，所有函数将开始返回最后一个函数返回的值，直到我们最终返回到调用原始的函数find。

为每个函数调用存储的确切数据量取决于调用约定和体系结构。在堆栈上推送数据会导致算法变慢，但这取决于算法。

这严格适用于不是尾部调用优化的递归。

来源

2017-01-08 15:47:22 nopjmp

大多数情况下，递归速度较慢，并且占用更多的堆栈。递归的主要优点是对于像树遍历这样的问题，它使算法变得更容易或更“优雅”。

检查出一些比较： Recursion vs Iteration

来源

2017-01-08 15:37:59

只有在编译器未优化的情况下，您的答案才为真。几乎所有的编译器都可以优化尾递归（尽管可能需要您启用这种优化）。在优化的情况下，这里应该没有区别。 – Cornstalks

递归版本的“find”与不递归版本之间有什么区别？

回答

相关问题