1

在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++ 很陌生）

4

2 回答 2

1

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

每个函数调用都会将数据推送到包含返回地址的堆栈上。这种情况一直持续到找到数据为止。这时候，所有的函数都会开始返回最后一个函数返回的值，直到我们最终回到调用原始函数的那个​​函数find。

为每个函数调用存储的确切数据量取决于调用约定和体系结构。将数据推送到堆栈上也会产生开销，这会使算法变慢，但这取决于算法。

这严格用于未优化尾调用的递归。

于 2017-01-08T15:47:22.970 回答
0

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

查看一些比较： 递归与迭代

于 2017-01-08T15:37:59.730 回答