Salut
Je vx savoir quelle est la relation entre les piles et la récursivité ?
Et si vous pouvez me donner un exemple sur la fonction factoriel et les piles
Version imprimable
Salut
Je vx savoir quelle est la relation entre les piles et la récursivité ?
Et si vous pouvez me donner un exemple sur la fonction factoriel et les piles
la récursivité se faisant sur la pile, sa limite est celle de la pile. D'autant plus si on a beaucoup de variables prises sur la pile..
Donc une fonction récursive à 30 paramètres appelées quelques milliers (10 aines de ??) de fois provoquera un crash...
La relation est donc d'être bien conscient de cette limite...
Dans mon cours de cette année au chapitre de la récursivité on l'a fais relire avec la notion des piles mais avec une explication très brève ...Citation:
Envoyé par juve1897
souviron34
Si tu peux expliquer en illustrant avec un exemple sur la factoriel
La récursivité utilise la mémoire automatique pour empiler les retours de fonctions, les paramètres et les résultats intermédiaires. C'est une manière, certes, 'élégante' de programmer, mais qui a des défauts :Citation:
Envoyé par yous18
- La taille de la mémoire automatique est limitée.
- Il n'y a pas de moyen standard de modifier ni même de connaitre la limite.
- En cas de débordement le comportement est indéfini.
- Il n'y a pas de moyen standard de savoir si on a atteint la limite.
merci mais je vx un exemple
on fais cette instruction en fonction
int fact(int n)
si on appel la fonction dans le main :Code:
2
3
4
5
quel sont les étape executer dans la pile ?Code:fact(4);
C'est une récursivité non-terminale.
Les étapes ici sont (sur une machine avec une pile, comme un Intel x86 ou un M68k) :
--dans le main:
empiler 4
empiler l'adresse de retour
--dans fact:
comparer 4 à 0
calculer 4-1 = 3
empiler 3
empiler l'adresse de retour
---
comparer 3 à 0
calculer 2-1 = 2
empiler 2
empiler l'adresse de retour
---
comparer 2 à 0
calculer 2-1 = 1
empiler 1
empiler l'adresse de retour
---
comparer 1 à 0
calculer 1-1 = 0
empiler 0
empiler l'adresse de retour
---
comparer 0 à 0
retourner 1
dépiler l'adresse de retour
---
calculer 2*1
retourner 2
dépiler l'adresse de retour
---
calculer 3*2
retourner 6
dépiler l'adresse de retour
---
calculer 4*6
retourner 24
dépiler l'adresse de retour
--dans le main:
suite...
Avant d'avoir un soucis avec la pile, tu auras un soucis avec le calcul de la factoriel en elle même.
On a : n!>=2^n.
Sur beaucoup de systèmes (ce n'est pas toujours le cas, attention), la taille d'un int est de 4 octets = 32 bits. Ce qui ne permet pas de représenter un entier plus grand que 2^33, donc tu ne peux pas calculer 33! (et encore, j'ai pris une énorme marge avec n!>2^n).
Donc si tu te limites aux valeurs où la factoriel est effectivement calculable, il n'y aura, normalement, pas de problème avec la pile... Mais l'algorithme étant tellement simple sans appel récursif, pourquoi s'en priver.
yous18 : Ta fonction plante si on fait fact(-1) :D
Tu sais, quatre octets ça fait 32 bits, pas 64...
PS: La factorielle dépasse la puissance de 2 à partir de n=4.
Ah oui, quel nase :mur:, trop d'architecture 64 bits tue le 32 bitsCitation:
Envoyé par Médinoc
Oui, comme je l'ai indiqué, la factoriel explose la puissance de deux, mais je voulais juste une inégalité pour montrer qu'on est sûr qu'à partir de 32, la valeur sera mauvaise. On pourrait avec un logiciel de calcul formel (ou autre d'ailleurs) calculer exactement la valeur limite ou avoir un bonne approximation en utilisant la formule de Stirling
merci les amis pour votre aide 8-)