Discussion :

[surame]

Bonjour

Dans une autre discussion de ce forum, j'ai trouvé le code ci-dessous d'une fonction qui détermine le nombre de chiffres d'un entier n passé en argument. Le programme fonctionne bien.

int nbr_chiffre(int n)
{
if(n<10) return 1;

int result;
result = 1+nbr_chiffre(n/10);
return result;
}

Je n'arrive pas à voir comment en utilisant la récursivité on peut incrémenter
la variable result à chaque appel de la fonction et en divisant l'argument par 10.

Est-ce que quelqu'un peut m'éclairer?

Merci bien. :

[seiron]

Pour bien comprendre ce bout de code, je n'aurai qu'un conseil a te donner

prend une feuille de papier et un crayon
choisi un valeur au hasard genre 1024
puis tu executes le programme avec ta tete, ta feuille et ton crayon

et la tu devrais voir le miracle s'accomplir, la recursivite c'est un bete appel de fonction

[-Raf-]

Le mieux a mon avis en général pour bien voir comment fonctionne un algorithme récursif c'est de le faire tourner à la main avec un cours exemple.

Prenons n=123 :

on a successivement :

nbr_chiffre(123)
{

123 > 10 donc tu es dans le deuxieme cas

tu vas retourner : 1 + la taille de 123/10 <=> 1 + la taille de 12 :

nbr_chiffre(12)
{

12>10 donc deuxieme cas.

tu vas retourner : 1 + la taille de 12/10 <=> 1 + la taille de 1 :

nbr_chiffre(1)
{

1<10
donc tu retoune 1;

}

nbr_chiffre(12) retourne 1+1;

}

nbr_chiffre(123) retourne 1+2;

}


(Je suis clair ? parce que c'est pas facile d'explique un algo récursif )

[surame]

Merci à RAF

C'est déjà beaucoup plus clair et j'ai ...presque tout compris ()
Juste un point encore un peu obscur:

tu vas retourner : 1 + la taille de 12/10 <=> 1 + la taille de 1 :

Comment la fonction "connaît elle" la taille de 1 qu'elle va retourner après le dernier appel?
C'est peut être tout simple à voir mais c'est précisement ce qui me pose problème.

[Médinoc]

En fait, ça, c'est comme la factorielle: C'est une chose tellement facile à faire en itératif que c'est bête de la faire en récursif.
L'utilité de la récursivité apparait plus évidente pour des fonctions comme le parcours d'arbres.

Note: Tu liras aussi parfois le terme "récursivité terminale", qui consiste à des appels récursifs dont le résultat est directement passé à return, sans aucun autre calcul. Ces fonctions sont particulières, car elles peuvent être optimisées par le compilateur pour supprimer la récursivité.

La fonction nbr_chiffre() n'a pas une récursivité terminale, puisqu'on fait une opération sur le résultat (une addition).

[Médinoc]

tu vas retourner : 1 + la taille de 12/10 <=> 1 + la taille de 1 :

Comment la fonction "connaît elle" la taille de 1 qu'elle va retourner après le dernier appel?

Parce que 1 est inférieur à 10.

[Thierry Chappuis]

En fait, ça, c'est comme la factorielle: C'est une chose tellement facile à faire en itératif que c'est bête de la faire en récursif.
L'utilité de la récursivité apparait plus évidente pour des fonctions comme le parcours d'arbres.

Note: Tu liras aussi parfois le terme "récursivité terminale", qui consiste à des appels récursifs dont le résultat est directement passé à return, sans aucun autre calcul. Ces fonctions sont particulières, car elles peuvent être optimisées par le compilateur pour supprimer la récursivité.

La fonction nbr_chiffre() n'a pas une récursivité terminale, puisqu'on fait une opération sur le résultat (une addition).

Voici une version récursive terminale (qui se traduit facilement en une version itérative. D'ailleurs, mon gcc 4.1.3 le fait tout seul avec l'option -O2):

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
26
27
28
29
30
31
32
#include <stdio.h>
 
int nbr_chiffres_rec(int n, int resultat)
{
    if (n < 10)
    {
        return resultat + 1;
    }
    else
    {
        return nbr_chiffres_rec(n/10, resultat + 1);
    }
}
 
int nbr_chiffres(int n)
{
    if (n < 0)
    {
        n = (-1) * n;
    }
    return nbr_chiffres_rec(n, 0);
}
 
 
int main(void)
{
    int nchiffres;
    nchiffres = nbr_chiffres(10);
    printf("n = %d\n", nchiffres);
 
    return 0;
}

Thierry

[-Raf-]

Oui c'est ce que j'ai apellé le premier cas,

Heu je sais plus comment ça s'appelle ? la condition d'arrêt de la récursivité ?

Ici ta condition c'est que dés que tu passe un nombre inférieur a 10, tu connais sa taille, soit 1, donc tu peut la retourner directement.

De même, si tu sais que tu vas toujours passer des nombres >=10, tu aurais put mettre comme condition d'arrêt :

if (n<100) return 2;

Jte conseilles vraiment de le faire tourner à la main sur papier! En écrivant bien tes appels de fonction.

[surame]

Merci pour vos réponses et votre aide.

D'accord, ici on peut largement utiliser et de manière plus simple l'itération.
En fait mon objectif est de d'essayer de comprendre le mécanisme de la récursivité sur des exemples simples.

Parce que 1 est inférieur à 10.

Hélas je ne vois toujours pas pourquoi résult est inréménté de 1 lors de chaque appel.

[surame]

OK!

j'ai posté mon derniers message avant de prendre connaissance de ta réponse.
C'est en fait ce point que "j'oubliais" de prendre encompte:

Ici ta condition c'est que dés que tu passe un nombre inférieur a 10, tu connais sa taille, soit 1, donc tu peut la retourner directement.


C'est clair maintenant.

Merci à RAF et à tous ceux qui ont bien voulu me répondre.

[-Raf-]

@ Thierry

La récursivité terminale telle que tu l'as présenté est-elle plus rapide que le premier algo qui était donné ou ça change rien en temps d'exécution ?

[Thierry Chappuis]

@ Thierry

La récursivité terminale telle que tu l'as présenté est-elle plus rapide que le premier algo qui était donné ou ça change rien en temps d'exécution ?

Le code assembleur généré par mon compilo a été automatiquement dérécursifié. Comparé à la fonction récursive non terminale postée plus haut, tu évites la création d'un contexte (empilement des arguments) pour chaque appel de fonction, ainsi que l'appel lui-même. Par ailleurs, la quantité de mémoire de pile utilisée par la version récursive terminale ne dépend pas de la profondeur des appels récursifs (O(1)). C'est clairement une optimisation intéressante.

Enfin, comme l'a rappelé Médinoc, pour une fonction aussi simple, il est avantageux d'écrire directement un code itératif. Mais si je devais écrire cette fonction en Haskell ou en OCaml, j'utiliserais sans hésiter la version récursive terminale.

Thierry

[-Raf-]

Heu je suis pas sur d'avoir compris pourquoi :

Par ailleurs, la quantité de mémoire de pile utilisée par la version récursive terminale ne dépend pas de la profondeur des appels récursifs (O(1))

Si tu fais un appel récursif, tu as bien un empilement de fonctions nan ?

Pour moi dans ta pile en mémoire, tu auras :


fonction(profondeur 1) + ses variables locales à la fonction
--------------------------------------------------------
...
---------------------------------------------------------
fonction(profondeur n - 2) + ses variables locales à la fonction
--------------------------------------------------------
fonction(profondeur n - 1) + ses variables locales à la fonction
--------------------------------------------------------
fonction(profondeur n) + ses variables locales à la fonction


Merci d'avance

[Médinoc]

Eh bien en récursivité terminale, tu n'en as pas besoin.
Le compilo, au lieu de faire (Empiler Paramètres) + (Empiler adresse de retour)+(Saut)+(Dépiler Paramètres), fait juste (Ecraser parametres avec les nouveaux) + (Saut), transformant la récursivité en une simple boucle.

[Thierry Chappuis]

Heu je suis pas sur d'avoir compris pourquoi :



Si tu fais un appel récursif, tu as bien un empilement de fonctions nan ?

Pour moi dans ta pile en mémoire, tu auras :


fonction(profondeur 1) + ses variables locales à la fonction
--------------------------------------------------------
...
---------------------------------------------------------
fonction(profondeur n - 2) + ses variables locales à la fonction
--------------------------------------------------------
fonction(profondeur n - 1) + ses variables locales à la fonction
--------------------------------------------------------
fonction(profondeur n) + ses variables locales à la fonction


Merci d'avance

Le compilateur reconnait la récusivité terminale et il sait qu'il peut optimiser dans ce cas en utilisant une simple boucle (ou l'équivalent assembleur utilisant des sauts). Essaie de regarder le code assembleur généré par gcc avec un niveau d'optimisation comme -O2, et tu constateras par toi-même que les appels récursifs ont disparu.

Voici le code généré chez moi:

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
26
27
nbr_chiffres_rec:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %ecx
	pushl	%esi
	movl	12(%ebp), %esi
	pushl	%ebx
	cmpl	$9, %ecx
	jle	.L4
	movl	$1717986919, %ebx
	.p2align 4,,7
.L3:
	movl	%ecx, %eax
	addl	$1, %esi
	imull	%ebx
	sarl	$31, %ecx
	sarl	$2, %edx
	subl	%ecx, %edx
	cmpl	$9, %edx
	movl	%edx, %ecx
	jg	.L3
.L4:
	leal	1(%esi), %eax
	popl	%ebx
	popl	%esi
	popl	%ebp
	ret

Je t'épargne les détails lié à l'assembleur, mais on voit assez clairement que notre fonction récursive a été transformée en code itératif (le corps de la boucle étant situé entre les étiquettes -L3 et .L4).

Thierry