如果我们通过引用传递变量，递归中使用的堆栈数量 space 是否为零？

Question

让我们有以下函数，它获取指向根的指针，return true 找到元素，false 否则

/**
* A method to test if an item is in a subtree.
* x is item to search for.
* ptr is the node that roots the subtree.
*/
template<typename T>
bool contains( const T & x, Node *t ) const
{
    if( ! ptr ) return false;
    else if( x < ptr->data ) return contains( x, ptr->left );
    else if( ptr->data < x ) return contains( x, ptr->right );
    else return true; // Match
}

使用的预期调用堆栈 space 预计为 O(log(N))，因为每次调用都会复制指针。

现在如果我们用下面的代码替换之前的代码，space 会使用零还是什么？

template<typename T>
bool contains( const T & x, Node* & ptr ) const
{
    if( !ptr ) return false;
    else if( x < ptr->data ) return contains( x, ptr->left );
    else if( ptr->data < x ) return contains( x, ptr->right );
    else return true; // Match
}

Answer 1

即使引用参数根本不占用堆栈 space （并且它们可以占用所述 space），这些参数的任何实现不执行尾递归优化的函数调用将至少在堆栈上有一个东西：指向 return 的位置的指针。实际上，没有 return 地址基本上就是尾调用。

基本上，您无法保证 C++ 中的尾调用。

如果我们通过引用传递变量，递归中使用的堆栈数量 space 是否为零？

Were the amount of the stack space, used in a recursion, zero if we would pass the vars by reference?

c++

recursion

binary-tree

callstack