Discussion :

[vdumont]

Voici un petit mot sur la récursivité qui pourrait être pratique autant dans une FAQ traitant les algos.

Je ne sais pas si le sujet est déjà abordé dans une autre FAQ mais bon, ca ne coûte pas grand chose de contribuer de toute façon!


Qu'est-ce que la récursivité?
La récursivité est le principe selon lequel une fonction s'appelle elle-même, en boucle, jusqu'à ce qu'une (ou plusieurs) conditions d'arrêt soient respectées.

Elle repose principalement sur les 3 points suivant

1. L'expression récursive (auto-appeler la fonction)
2. La condition d'arrêt (quand arrête-t-on de boucler?)
3. La convergence (ce qui nous amène vers la condition d'arrêt)

Voici un exemple simplet et concret.

Supposons que l'on veut calculer le factorielle d'un nombre positif n (par exemple: le factoriel de 6 est 6*5*4*3*2*1 = 720).

La fonction récursive pourrait ressembler à quelque chose du genre, dans une notation C:

Code :

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

1
2
3
4
5
long factorielle(unsigned int n)
{
   if (n == 1 || n == 0) return 1l;
   return ((long) n * factoriel(n-1));
}

La condition d'arrêt dans l'exemple ci-haut est (n == 1 OU n == 0)
L'expression récursive est le deuxième return, soit return (n * factoriel(n-1));
La convergence est donc intégré à l'expression récursive dans ce cas-ci (et c'est souvent le cas)
Ainsi, on bouclera les appels à factorielle(int) jusqu'à temps que le nombre passé en paramètre soit 1.

Voila une façon simple et efficace de calculer le factorielle d'un nombre positif en utilisant la récursivité. Imaginez maintenant tout ce que l'on peut faire avec la récursivité



J'espère que ca sera utile à quelqu'un!


EDIT: FAQ algos et non C/C++

[Thierry Chappuis]

Bonjour,

Une FAQ est en train de se créer sur le forum Algorithmique, et je me demande si elle ne serait pas plus adaptée pour héberger une Q/R sur la récursivité. En effet, je pense qu'il s'agit là d'une technique qui n'est pas propre ni au langage C ni à C++, mais dont la portée peut être étendu à n'importe quel langage structuré.

En tout cas, je verrais bien une Q/R sur la récursivité, en pseudo-code sur la FAQ d'algo.

Meilleures salutations

Thierry

[vdumont]

C'est également ce que je me suis dit après y avoir repenser. C'est plus un concept que quelque chose de relié directement à un langage.

Alors pour la FAQ Algo alors!

[millie]

Yop, voilà, je ne savais pas si ça allait être déplacé ou si tu allais reposter.

J'avais des petites remarques.

- Notation C (et non algorithmique), enfin, tu n'as peut être pas encore eu le tps de changer

- Même en C, le cast est assez mal placé (même si ça marche), fact renvoit un long, donc return (long) (n * factoriel(n-1)); devrait plutôt être return ((long)n * factoriel(n-1)); vu qu'il y a une multiplication par n.

- La condition if (n < 0) exit(1); est inutile, il suffit de prendre en entrée un unsigned int (ou spécifier en algorithmique une précondition à l'appel, c'est à dire n : Entier positif)

- C'est factorielle et non pas factoriel


Peut-être faire une description des fonctions récursives terminales et non terminales.

Peut-être préciser (enfin, là, ce n'est plus de l'algo) que certains langages ne se pretent pas bien aux appels récursifs. Par exemple le C/C++, car ils mettent les valeurs des appels de fonctions sur la pile, et il peut vite y avoir des débordements de piles si c'est mal fait. De plus, je ne suis pas sûr que le langage C utilise les propriétés de récursivité terminal ou non.

[vdumont]

Merci de ton avis millie, je vais essayer de corriger cela et reposter.

[HanLee]

Peut-être préciser (enfin, là, ce n'est plus de l'algo) que certains langages ne se pretent pas bien aux appels récursifs. Par exemple le C/C++, car ils mettent les valeurs des appels de fonctions sur la pile, et il peut vite y avoir des débordements de piles si c'est mal fait. De plus, je ne suis pas sûr que le langage C utilise les propriétés de récursivité terminal ou non.

Les compilateurs C/C++ récents détectent les cas de récursivité terminale il me semble.

[millie]

Les compilateurs C/C++ récents détectent les cas de récursivité terminale il me semble.

Oui, je ne suis pas sûr non plus. Par contre, je suis sûr qu'il met les arguments des fonctions sur la pile, donc c'est pas très bon si il y a beaucoup d'appel.

[Jean-Marc.Bourguet]

Les compilateurs C/C++ récents détectent les cas de récursivité terminale il me semble.

Dès qu'on utilise des destructeurs en C++, les cas de récursivité terminale se font rares.

[Jean-Marc.Bourguet]

Oui, je ne suis pas sûr non plus. Par contre, je suis sûr qu'il met les arguments des fonctions sur la pile, donc c'est pas très bon si il y a beaucoup d'appel.

Les compilateurs qui implémentent la suppression des appels terminaux (qu'ils soient récursifs ou non -- on peut faire la même chose dès que l'appel est la dernière chose faite dans la fonction, ajuster la pile peut être plus délicat si le nombre de paramètres est différents) remplacent les appels finaux par des modifications de leurs paramètres et un saut.

[PRomu@ld]

Par contre, je suis sûr qu'il met les arguments des fonctions sur la pile, donc c'est pas très bon si il y a beaucoup d'appel.

Les compilateurs qui implémentent la suppression des appels terminaux ...

Comme l'a dis Jean-Marc, les cas terminaux ne sont pas tous gérés de la même façon. Il faut donc savoir comment fonctionne son compilateur avant de conclure.

[HanLee]

Dès qu'on utilise des destructeurs en C++, les cas de récursivité terminale se font rares.

T'as pas des exemples ? J'vois pas trop ce que tu voulais dire.

[Jean-Marc.Bourguet]

T'as pas des exemples ? J'vois pas trop ce que tu voulais dire.

Le destructeur des variables automatiques d'exécutant à la sortie des fonctions après tout le code de la fonction, l'appel récursif à la fonction peut difficilement être terminal: les destructeurs doivent s'exécuter après.