Discussion :

[Kikokimo]

Salut !

Donc ! Je suis coincé sur un exercice sur la récursivité qui demande de proposer une fonction qui "teste si un mot contient un nombre pair ou non d'un caractère C donné".

J'ai déjà pensé à ajouter une autre variable qui va contenir le nombre d'occurrences du caractère dans les paramètres de la fonction mais je ne pense pas que ce soit vraiment la meilleure solution .

Est-ce que c'est possible de trouver un algorithme récursif de cette fonction en passant juste le caractère et la chaîne comme paramètres ?

Merci !

[Dr.Who]

la récursivité est analogue à la masse noire de l'univers.

en gros, c'est la, mais ça semble ne servir à rien.


bref.

trouver le nombre d'occurence d'un caractère dans une chaine et dire si il est pair ou impair ...

Code :

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

1
2
3
4
5
6
7
8
9
10
function CountLoop(const S: string; const C: char; var Count: integer): boolean;
var L, N : integer;
begin
  count := 0;
  L := Length(S)-1;
  for N := 0 to L do
    if S[N] = C then
      inc(Count);
  result := (Count and $1) = $0; // true : Count est pair.
end;

sincerement, faire une version recursive de ce truc ... ça sert ... à rien.

la récursivité est un truc à connaitre, à comprendre, mais rien ne sert de s'attarder dessus, vus que c'est anti-performant (à cause des call et de la gestion de la pile), sans parler des trop fréquente erreur de débordement de pile avec une récursion trop gourmande.

d'ailleurs trois exemples sympathique pour tester la récursivité sont :

1 - l'exploration des sous-répertoires
2 - Le calcul de la factorielle de N
3 - Le calcul de la suite de Fibonacci.

les exemples ou la récursivité se montre utile se compte sur les doigts de la mains (et des pieds au cas ou).

dans l'exemple que tu cite, appeler le compteur de façon récursive serait une perte de temps et de performances notable.

exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
function CountRecurs(const S: string; const Current: integer; const CompareChar: char): integer;
begin
  if Current > Length(S) then
    exit;
 
  result := 0;
 
  if S[Current] = CompareChar then
    result := 1;
 
  result := result + CountRecurs(S, Current+1, CompareChar);
end;

et j'introduis une troisieme fonction en boucle plus performante :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function CountLoopPerf(const S: AnsiString; const C: AnsiChar; var Count: integer): boolean;
var pB : ^byte;
    Cb : byte;
begin
  pB := @S[1];
  Cb := byte(C);
  count := 0;
  repeat
    if pB^ = Cb then
      inc(Count);
    inc(pB);
  until pB^ = 0;
  result := (Count and $1) = $0; // true : Count est pair.
end;

test de performances :

CountLoopPerf : 5.2/440
CountLoop : 8.9/440
CountRecurs : 118.0/440

pour les autres exemple cités (factorielles, fibonacci etc) les performances seront toujours du même accabit.
les boucles sont et seront toujours plus rapides.

[Kikokimo]

Merci Dr.Who Pour cette réponse claire et très explicite !

C'est juste qu'on est sur le chapitre de la récursivité en classe que j'ai penser à le faire avec une manière cette méthode, sinon j'aurais utiliser les boucles car comme tu m'a dit la récursivité semble juste compliquer les choses sauf dans certain problèmes mathématiques comme suites récurrentes etc..

encore merci pour ta réponse!

ps : je crois fallait que je poste dans la catégorie "Turbo Pascal" car c'est pas vraiment sa ce qu'on fait en classe (c'est du delphi sa je pense ? ), mais j'ai compris comme même.

[Dr.Who]

Delphi, Turbo Pascal, à peu de chose prés, c'est nativement la même chose.

ici la fonction utilsant des AnsiString/AnsiChar c'est pour Delphi >= 2007.

en turbo pascal sera à remplacer par "string" et "char"

note comment les performances sont meilleur en utilisant le type byte plutôt que char.
cela s'explique que les manipulations de chaines et de caractères sont plus longues que les manipulations d'octets et de bits.

retiens bien cet exemple car si un jours on te demande une fonction de manipulation de chaine performante, il faudra que tu en vienne à cela.

sinon retiens bien aussi que tout ce qui est fonction recursive, peu s'ecrire en version boucle, plus rapide et performante.
j'y ajoute :
la recherche des nombres premiers
la recherche des diviseurs comuns
la recherche des multiples de N
la recherche de la N-iéme décimale de PI
etc.

[Kikokimo]

Oui j'ai remarqué que y a pas vraiment une différence entre delphi et turbo pascal puisque les deux sont basés sur pascal.

Mais j'ai pas vraiment compris comment t'as utiliser le type byte à la place de char car y a des notations que j'ai jamais rencontré par exemple
-Quand tu déclare une variable de type " ^byte " Sa veut dire quoi exactement ? (sorte de pointeur comme en c++ ? xD )
-et "Cb := byte(c)" Sa met le code ascii de c dans "Cb" comme la fonction ord() ?

Désolé si mes questions semblent un peu banales mais je débute encore

[Dr.Who]

alors :

^ c'est effectivement un pointeur.

^byte = pointeur sur byte
^integer = pointeur sur integer
^string = pointeur sur string

vois ici, ^ comme un type adresse (donc pointeur) associé à l'autre symbole "@" comme "at" (à : à l'adresse)
un peu comme les adresse mail :
Jean@hotmail.fr -> jean "at" hotmail.fr qu'on peu traduire "jean chez hotmail.fr"

char etant en 8 bits et byte etant en 8 bits egalement, je peux donc pointé un byte sur un char ... (mais c'est grossier de le faire pendant un défilé militaire).

Cb := byte(C);

est un transtypage, si le type est compatible (de la même taille ou plus petit).

en gros, ici, il faudrait aborder l'assembleur pour mieux comprendre.

si je reste en Char et String, il y a de grande chance pour que les registre utilisé soit SI, ESI, DI, EDI par exemple qui sont des registres un peu lents.
en travaillant en byte par contre je vais forcer l'utilisation des registres d'entiers AL, CL, DL, BL appartenant respectivement à EAX, ECX, EDX, EBX.
qui sont les registres les plus rapides.
tout les instructions de comparaison, de calcul etc seront donc plus rapide d'execution et nous gagnerons quelques cycles processeurs par ci par la.

et on vois bien le gains de quasiment 35% par rapport à la version Char/string.
on pourrait même aller plus loin si on etait sur de travailler uniquement avec des chaines trés longues et en se servant directement d'un type 32 bits (LongWord) pour manipuler les chaines 4 octets par 4 octets.
ce qui serai donc trés rapide même avec des chaines de plusieurs mega-octets.