c++ - 如何使用 void 类型处理递归回溯返回

Question

为了概括这个问题，我借用了 Zelenski CS 类(class)讲义中的 Material 。而且，它与我的具体问题相关，因为几年前我从另一位讲师那里上过这门课，并学习了这种 C++ 方法。讲义是here .我对 C++ 的理解很低，因为我偶尔会用到它。基本上，有几次我需要编写程序时，我会返回类 Material ，找到类似的内容并从那里开始。

在此示例(第 4 页)中，Julie 正在字符串函数中使用递归算法查找单词。为了减少递归调用的次数，她添加了一个决策点 bool containsWord()。

string FindWord(string soFar, string rest, Lexicon &lex)
{
  if (rest.empty()) {
   return (lex.containsWord(soFar)? soFar : "");
  } else {
   for (int i = 0; i < rest.length(); i++) {
     string remain = rest.substr(0, i) + rest.substr(i+1);
     string found = FindWord(soFar + rest[i], remain, lex);
     if (!found.empty()) return found;
   }
  }
 return ""; // empty string indicates failure
}

为了增加使用该算法的灵 active ，是否可以将其实现为 void 类型？

void FindWord(string soFar, string rest, Lexicon &lex, Set::StructT &words)
{
  if (rest.empty()) {
    if (lex.containsWord(soFar)) //this is a bool
       updateSet(soFar, words); //add soFar to referenced Set struct tree
  } else {
   for (int i = 0; i < rest.length(); i++) {
     string remain = rest.substr(0, i) + rest.substr(i+1);
     return FindWord(soFar + rest[i], remain, lex, words); //<-this is where I am confused conceptually
   }
  }
 return; // indicates failure
}

而且，如果没有返回会怎样

void FindWord(string soFar, string rest, Lexicon &lex, Set::StructT &words)
{
  if (rest.empty()) {
    if (lex.containsWord(soFar)) 
       updateSet(soFar, words); //add soFar to Set memory tree
  } else {
   for (int i = 0; i < rest.length(); i++) {
     string remain = rest.substr(0, i) + rest.substr(i+1);
     FindWord(soFar + rest[i], remain, lex, words); //<-this is where I am confused conceptually
   }
  }
}

Answer 1

第一个代码片段将尝试 rest 的所有排列, 附加到 soFar 的初始值(可能是一个空字符串？)。它会在找到第一个单词时停止，该单词位于 lex 中。 .该词将在找到时立即返回，搜索将在此时被缩短。如果没有人在 lex ，当所有 for 都返回时，最终将返回空字符串循环已经运行到最后。

第二个片段只会尝试一个词:初始soFar的串联和 rest字符串。如果该连接字符串在 lex 中, 它会调用 updateSet用它。然后它会返回，表示失败。不会执行进一步搜索，因为 return从 for 里面循环是无条件的。

所以这两个函数是完全不同的。要使第二个代码的行为与第一个相同，您需要它返回其他内容以指示成功，并且仅从 for 中返回当 FindWord 时循环调用返回值表示成功。显然，void不能用来发信号failure和 success .至少，你需要返回 bool的值(value)。

如果没有返回，您的第三个代码将执行详尽搜索。 rest 的初始字符串值的所有可能排列将被尝试，在词典中找到。

你可以像这样想象发生了什么:

FindWord:   soFar=""     rest=...........
    for:    i=...    rest[i]=a
       call findWord

FindWord:   soFar=a       rest=..........
    for:    i=...    rest[i]=b
       call findWord

FindWord:   soFar=ab       rest=.........
    for:    i=...    rest[i]=c
       call findWord
       if return, the loop will be cut short
       if not, the loop continues and next i will be tried

 ......

FindWord:   soFar=abcdefgh...      rest=z
    for:    i=0      rest[0]=z
       call findWord

FindWord:   soFar=abcdefgh...z      rest=""      // base case
    // for:    i=N/A    rest[i]=N/A
    if soFar is_in lex                           // base case
      then do_some and return soFar  OR  success
      else             return ""     OR  failure

每次达到基本情况时(rest 为空)我们都有n+1 FindWord堆栈上的调用帧，用于 n首字母rest字符串。

每次触底时，我们都会从 rest 中选取所有字母.执行检查以查看它是否在 lex 中, 并且控件返回上一级。

所以如果没有返回，每个for循环将运行到结束。如果返回是无条件的，则只会尝试一种排列——普通排列。但如果返回是有条件的，整个事情只会在第一次成功时停止。