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

Question

为了概括这个问题，我从Zelenski CS课程讲义中借用材料。而且，这与我的具体问题有关，因为几年前我从另一位讲师那里学习了这门课程并学习了这种C ++方法。讲义是here。我对C ++的理解很低，因为偶尔使用它。基本上，我需要编写一个程序的几次我返回到类材料，发现类似的东西并从那里开始。

在这个例子中（第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
}

为了增加使用此算法的灵活性，可以将其实现为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值。

如果没有返回，您的第三个代码将执行详尽的搜索。将尝试在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循环将运行到它的结尾。如果回报是无条件的，那么只会尝试一种排列 - 这是微不足道的。但如果回报是有条件的，整个事情只会在第一次成功时停止。