在 Accelerated C++ Programming 一书中,第 205 页,有以下两个 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);
}
通过使用 Kerrek 建议的编译器资源管理器,我得到了以下信息
非递归 https://godbolt.org/g/waKUF2
递归 https://godbolt.org/g/VKNnYZ
编译后好像一模一样? (如果我正确使用该工具..抱歉,我是 C++ 的新手)
最佳答案
递归函数会在栈上添加额外的元素。这可能会导致 stackoverflow 错误,具体取决于开始递归之前堆栈的状态和递归的次数。
每个函数调用都会将数据压入堆栈,其中包括返回地址。这一直持续到找到数据为止。这时候,所有的函数都会开始返回最后一个函数返回的值,直到我们最终回到调用原始find
的函数。
为每个函数调用存储的确切数据量取决于调用约定和体系结构。将数据插入堆栈也会产生开销,这会使算法变慢,但这取决于算法。
这严格适用于未优化尾调用的递归。
关于c++ - "find"的递归版本和非递归版本有什么区别?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41534341/