如何使这个搜索函数非递归

Question

我试图把这个递归函数变成一个非递归函数。这是一个二叉搜索树的搜索函数。我知道让它递归是很自然的，但为了学习的目的，我想让它非递归。我怎么能这么做?提前感谢!

    bool Search(BstNode* root, string data) {
    if (root == NULL) return false;
    else if (root->data == data) return true;
    else if (data <= root->data) return Search(root->left, data);
    else return Search(root->right, data);
}

Answer 1

这是一个使递归算法非递归的机械方法。

bool Search(BstNode* root, string data) {
  if (root == NULL) return false;
  else if (root->data == data) return true;
  else if (data <= root->data) return Search(root->left, data);
  else return Search(root->right, data);
}

绑定状态(参数和局部变量):

bool Search(BstNode* root, string data) {
  struct State {
    BstNode* root;
    string data;
  };
  State state{root, data};
  if (state.root == NULL) return false;
  else if (state.root->data == state.data) return true;
  else if (data <= state.root->data) return Search(state.root->left, state.data);
  else return Search(state.root->right, state.data);
}

将正文绕入循环:

bool Search(BstNode* root, string data) {
  struct State {
    BstNode* root;
    string data;
  };
  State state{root, data};
  while(true) {
    if (state.root == NULL) return false;
    else if (state.root->data == state.data) return true;
    else if (data <= state.root->data) return Search(state.root->left, data);
    else return Search(state.root->right, data);
  }
}

用改变状态替换结束递归(return recursive_call)的情况并继续:

bool Search(BstNode* root, string data) {
  struct State {
    BstNode* root;
    string data;
  };
  State state{root, data};
  while(true) {
    if (state.root == NULL) return false;
    else if (state.root->data == state.data) return true;
    else if (data <= state.root->data) {
      state = {state.root->left, state.data};
      continue;
    } else  {
      state = {state.root->right, state.data};
      continue;
    }
  }
}

现在，如果有更多的递归调用不是return recursive_call，添加一个手动的状态堆栈并push/pop它，而不是改变back。将返回状态的位置作为void**包含在带有标签的代码中。

这里不需要，所以我就不做了

Answer 2

通常可以通过将递归调用"放在"堆栈上，然后使用

使递归函数具有一般迭代性

while !stack.is_empty() do stack.pop()之类的

，因为这是编译器要做的事情，如果递归没有发生在机器代码级别