通过引用传递向量的尾递归

Question

考虑一个尾递归的例子

int foo(vector<int> &vec, int n)
{
    if (n == 1) return vec[0];      
    vector<int> new_vector = createNewVector(vec);              
    return foo(new_vector, n-1);
}

其中 createNewVector(vec) 是 returns 与 vec 大小相同的新向量的任何函数。

我担心编译器无法将其检测为尾递归，因为 vec 是通过引用传递的（无法删除前一个堆栈帧，因为 vec 引用指向前一个 new_vector).在这种情况下，用于此递归的内存将为 O(n*vec.size())，因为每个先前的堆栈帧都包含 vec.size() 个元素。

这是真的吗，或者这个函数可以优化为尾递归？

Answer 1

尾递归 (TCO) 在这种情况下是不可能的。 new_vector 析构函数必须在递归调用 return 之后调用，这完全消除了 TCO 的任何可能性。

一般来说，自动对象的析构函数使得编译器在非平凡类型的自动变量起作用时参与 TCO 变得非常棘手，并且在您的示例中按值或按引用传递向量不会差异 - TCO 仍然没有发生。

通过引用传递向量的尾递归

Tail recursion with a vector passed by reference

c++

recursion

tail-recursion

pass-by-reference