2

我试图把这个递归函数变成一个非递归函数。这是一个来自二叉搜索树的搜索函数。我知道让它递归是很自然的，但出于学习目的，我想让它成为非递归的。我怎么能这样做？提前致谢！

    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);

}
4

2 回答 2

5

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

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);
  }
}

将尾端递归（返回 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，添加一个手动堆栈状态并推送/弹出它而不是改变后面。void**在带有标签的代码中包含返回状态的位置。

这不是必需的，所以我不会费心去做。

于 2016-10-11T20:34:45.917 回答
1

您通常可以通过基本上将递归调用“放入”堆栈，然后使用

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

因为这本质上是编译器将执行的操作，因为递归不会发生在机器代码级别

于 2016-10-11T20:35:03.517 回答