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.

[-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]

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.

[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.

[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