Discussion :

[Kriegor D Will]

Bonjour,

J'ai un exercice que je n'arrive pas à résoudre sur la récursivité, voici l'énoncé :

Écrire une fonction récursive int SousChaine(char* aiguille, char* botteDeFoin) qui recherche une chaîne aiguille dans une chaîne botteDeFoin. La fonction renvoie l'indice de début de la première occurrence trouvée si la chaîne aiguille apparaît dans botteDeFoin et -1 sinon.
Si aiguille contient "bra" et botteDeFoin contient "abracadabra", l'appel SousChaine(aiguille, botteDeFoin) renvoie 1.

Donc j'ai compris le principe de l'exercice. Cependant, je ne comprend pas comment faire l'appel récursif avec cette fonction. D'habitude on utilisait une autre variable dans l'appel que l'on modifie à chaque appel, là il n'y a que les deux chaînes alors je ne vois pas trop comment exécuter l'appel récursif. Au début je me débrouillai pour changé le pointeur de chaque chaîne pour qu'ils pointent respectivement vers la case suivante, mais c'est sûrement pas ça...

Quelqu'un pourrait m'aider ou me mettre sur la bonne voie ?

Merci.

[Metalman]

Tu vas devoir avancer dans la chaîne caractère par caractère, et remonter le numéro du caractère, ou -1...

Quelquechose comme ça pourrait te donner la condition "principale" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
  if (botte[i] == NULL)
    return (-1);
  return (fonction(i + 1, aiguille, botte));

Tu peux aussi commencer à réfléchir que tu dois avancer dans 2 chaînes...
Donc 2 indices seront peut être nécessaires !
...2 indices à faire évoluer au fur et à mesure des appels, cela ressemble à :

• Une fonction principale qui fera démarrer les 2 indices à 0
• Une sous-fonction qui fera évoluer les 2 indices si elle trouve que aiguille[j] == botte[i] !

[imperio]

J'aurais plutôt fait ça comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
if (botte[i] == '\0')
    return 0;
  return (SousChaine(aiguille, botte + i) + 1);

Pas besoin de créer d'autre fonction du coup.

[Metalman]

Ok je me suis trompé sur le NULL, mais tu ne renvoies pas -1 si c'est introuvable....

J'ai en effet oublié de renvoyer un autre "vrai" nombre (car je n'ai pas écrit la comparaison exacte), mais tu utilises un "i" qui n'existe pas dans ton cas.

L'intérêt de la "fonction chapeau" c'est justement d'ajouter les paramètres nécessaires à la récursivité.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// i == index sur la chaîne principale
// j == index sur la sous-chaîne
int Cherche(char *aiguille, char *botte, int i, int j)
{
  if (aiguille[j] == '\0') //On a trouvé
    return (i - j);
  else //On cherche encore
  {
    if (botte[i] == '\0')
      return (-1); //On est arrivé au bout sans trouver
    if (aiguille[j] == botte[i])
      return (Cherche(aiguille, botte, i + 1, j + 1)); //On a reconnu 1 char commun
    else
      return (Cherche(aiguille, botte, i + 1, 0)); // On n'a pas reconnu de char commun
  }
}
 
int SousChaine(char *aiguille, char *botte)
{
  return (Cherche(aiguille, botte, 0, 0));
}

EDIT : mince... c'est la réponse...
Mais ça m'a fait plaisir de me décrasser l'esprit côté récursif...

[imperio]

Je voyais ça plutôt comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int SousChaine(const char *aiguille, const char *botte)
{
  int i = 0, j = 0;
 
  if (!aiguille || !botte)
    return 0;
  while (botte[i])
  {
      if (botte[i] == aiguille[0])
      {
         j = 1;
         ++i;
         while (aiguille[j] && botte[i] && aiguille[j] == botte[i])
         {
            ++j;
            ++i;
         }
         if (!aiguille[j])
           return SousChaine(aiguille, botte + j) + 1;
      }
      else
        ++i;
  }
  return 0;
}

Comme je disais, pas besoin de 2e fonction donc.

Je renvoie 0 si je ne trouve pas d'occurence mais on peut très bien bidouiller pour renvoyer -1 sinon, c'est juste inutile.

[Metalman]

Euh.... l'intérêt du récursif c'est "justement" de n'avoir strictement aucune boucle... ^^'

EDIT : mais en effet tu économise le nombre de fonctions et de paramètres

[imperio]

Strictement aucune ? Bizarre, j'ai toujours vu ça comme un "truc" pour se faciliter la vie. Dans le cas présent ça m'a évité de créer une variable de plus pour compter le nombre d’occurrence. Bon okay, mon exemple n'était pas forcément extra pour de la récursivité...

[Metalman]

Dans la pratique oui tu peux en avoir un peu !

Mais ça casse généralement la logique "récursive" qui reste du filtrage de cas et de l'avancement dans les éléments traités.
[Donc oui tu peux faire un parser récursif, où la partie récursive traitera uniquement certains bouts du problème, et le reste sera plein de boucles. Mais on ne mélange quasiment jamais dans les mêmes blocs le récursif et les boucles]

Et vu que ça sent l'exercice d'école à plein nez, c'est du full-récursif-sans-aucune-boucle...

[ternel]

Le récursif normal serait plus dans le genre de ceci, je pense:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int SousChaine(const char *aiguille, const char *botte) {
    if (strlen(botte)<strlen(aiguille)) return -1;
    if (/*aiguille est préfixe de botte*/) return 0;
    int position = souschaine(aiguille, botte+1);
    return position<0 ? position, 1 + position;
}

le codage de la détection de préfixe peut se faire immediatement avec strncmp, ou manuellement, avec une boucle courte.

Une fonction récursive avec un indice linéaire est une boucle for déguisée.

La récursion sert souvent à représenter un graphe acyclique (et orienté) de situations à étudier.
Ce en quoi, on peut la remplacer magiquement par un while - switch

[Metalman]

leternel a remonté une bonne remarque : les vérifications que bottes et aiguilles ne sont pas NULL, ni trop courts... dans mon cas c'est à rajouter dans la fonction très courte pour immédiatement retirer les cas foireux.