Comment sont gérés les retours en arrière récursifs avec le type void ?

Question

Pour généraliser cette question, j'emprunte le matériel d'un polycopié du cours de CS de Zelenski. Et, il est pertinent pour ma question spécifique puisque j'ai suivi le cours d'un autre instructeur il y a plusieurs années et j'ai appris cette approche du C++. Le document est le suivant aquí . Ma compréhension du C++ est faible puisque je l'utilise occasionnellement. En fait, les quelques fois où j'ai eu besoin d'écrire un programme, je suis retourné au matériel de cours, j'ai trouvé quelque chose de similaire et j'ai commencé à partir de là.

Dans cet exemple (page 4), Julie cherche un mot en utilisant un algorithme récursif dans une fonction de chaîne. Pour réduire le nombre d'appels récursifs, elle a ajouté un point de décision 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
}

Pour ajouter de la flexibilité à l'utilisation de cet algorithme, peut-on l'implémenter en tant que type 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
}

Et, pourquoi pas sans les retours

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

Le premier fragment de code va essayer toutes les permutations de rest ajouté à la valeur initiale de soFar (probablement une chaîne vide ?). Il s'arrêtera sur le premier mot trouvé qui est dans lex . Ce mot sera renvoyé dès qu'il sera trouvé, et la recherche sera interrompue à ce moment-là. Si aucun mot n'est présent lex La chaîne vide sera éventuellement renvoyée, lorsque toutes les chaînes de caractères de l'option for Les boucles ont suivi leur cours jusqu'au bout.

Le second fragment n'essaiera qu'un seul mot : la concaténation de l'initiale soFar y rest des cordes. Si cette chaîne concaténée est dans lex il appellera updateSet avec elle. Puis il reviendra, indiquant un échec. Aucune autre recherche ne sera effectuée, car le return de l'intérieur de la for La boucle est inconditionnelle.

Ces deux fonctions sont donc complètement différentes. Pour que le second code se comporte comme le premier, il faut qu'il renvoie quelque chose d'autre pour indiquer un succès, et qu'il ne soit renvoyé qu'à l'intérieur de la fonction for boucle quand FindWord La valeur de retour de l'appel indique un succès. Évidemment, void ne peut pas être utilisé pour signaler failure y success . Au minimum, vous devez retourner bool valeur pour cela.

Et sans les retours, votre troisième code effectuera une recherche exhaustive. Toutes les permutations possibles de la valeur initiale de la chaîne de caractères rest seront jugés, à trouver dans le lexique.

Vous pouvez visualiser ce qui se passe comme ça :

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

Chaque fois que le cas de base est atteint ( rest est vide), nous avons n+1 FindWord les trames d'appel sur la pile, pour n les lettres de l'initiale rest chaîne.

A chaque fois que nous atteignons le fond, nous avons pris toutes les lettres de rest . La vérification est effectuée pour voir si elle est en lex et le contrôle revient à un niveau supérieur.

Donc s'il n'y a pas de retour, chaque for la boucle se déroulera jusqu'à son terme. Si le retour est inconditionnel, une seule permutation sera essayée - la permutation triviale. Mais si le retour est conditionnel, la boucle ne s'arrêtera qu'au premier succès.