c++ - C++中的高性能递归函数

Question

我正在学习C++，并且在玩链表。
考虑以下极其简单的实现:

static std::size_t n_constructors {0};


template <typename T>
class list {
public:
    list(T n) : item{n} { n_constructors++; }
    list(T n, list* l) : item{n}, next {l} { n_constructors++; }
    list(const list&);
    ~list() { delete next; }
    void insert(T n);
    void print() const;
    list reverse() const;
    list reverse_iter() const;
private:
    T item;
    list* next {nullptr};
};


template <typename T>
list<T>::list(const list& src)
    :
    item {src.item}
{
    n_constructors++;
    if (src.next) {
        next = new list {*src.next};
    }
}


template <typename T>
void list<T>::insert(T n) {
    if (next == nullptr)
        next = new list {n};
    else
        next->insert(n);
}


template <typename T>
void list<T>::print() const {
    std::cout << item << " ";
    if (next)
        next->print();
    else
        std::cout << std::endl;
}


template <typename T>
list<T> list<T>::reverse() const {
    if (next) {
        auto s = next->reverse();
        s.insert(item);
        return s;
    } else {
        return list {item};
    }
}


template <typename T>
list<T> list<T>::reverse_iter() const {
    auto sptr = new list<T> {item};
    auto prev = next;
    auto link = next;
    while (link) {
        auto tmp = new list<T>(link->item, sptr);
        link = link->next;
        prev = link;
        sptr = tmp;
    }
    return *sptr;
}

如您所见，我编写了两个反向函数:一个迭代函数和一个递归函数。
为了测试它们，我尝试了以下方法:

int main() {
    list<int> s{1};
    for (int i = 2; i < 10000; ++i)
        s.insert(i);
    std::cout << "initial constructor\n";
    std::cout << "called " << n_constructors << " constructors.\n";
    auto t0 = std::chrono::high_resolution_clock::now();
    auto s2 = s.reverse_iter();
    auto t = std::chrono::high_resolution_clock::now();
    std::cout << "iterative reverse\n";
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(t - t0).count() <<" ms\n";
    std::cout << "called " << n_constructors << " constructors.\n";
    t0 = std::chrono::high_resolution_clock::now();
    auto s3 = s.reverse();
    t = std::chrono::high_resolution_clock::now();
    std::cout << "recursive reverse\n";
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(t - t0).count() <<" ms\n";
    std::cout << "called " << n_constructors << " constructors.\n";
}

这是我的基准测试的典型结果(与g++ 9.3.0编译，通过 -O2打开了optimiser):

initial constructor
called 9999 constructors.
iterative reverse
0 ms
called 29997 constructors.
recursive reverse
1692 ms
called 50034995 constructors.

性能上的差异是惊人的。
我猜想递归版本的问题在于分配的数量要多得多，所以我实现了move构造函数:

template <typename T>
list<T>::list(list&& src)
    :
    item {src.item},
    next {src.next}
{
    n_constructors++;
    src.next = nullptr;
    src.item = 0;
}

结果如下:

initial constructor
called 9999 constructors.
iterative reverse
0 ms
called 29997 constructors.
recursive reverse
90 ms
called 49994 constructors.

很好，现在至少递归函数执行与迭代函数一样多的分配。
但是，性能差异仍然很大。
我再次尝试使用100000个元素:

initial constructor
called 99999 constructors.
iterative reverse
7 ms
called 299997 constructors.
recursive reverse
9458 ms
called 499994 constructors.

我认为，与迭代相比，递归反向更具可读性和优雅性。
为什么递归版本这么慢？
我可以做些什么使它更快吗？
编辑
正如威尔·尼斯(Will Ness)在评论中所建议的，我添加了两种算法的经验渐近增长图。

Answer 1

您不仅要在递归和迭代之间进行测试，还要在增长顺序不同的两种算法之间进行测试。
您的reverse的复杂度为T(n)= T(n-1)+ O(n)，因此链接数为平方。您的reverse_iter仅具有线性复杂度。因此，这种比较是不公平的。