Discussion :

[yous18]

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

[souviron34]

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

[yous18]

A priori, je serait tenté de dire aucune, mais bon as tu un enoncé plus precis?

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

souviron34
Si tu peux expliquer en illustrant avec un exemple sur la factoriel

[Emmanuel Delahaye]

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é 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 :

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

[yous18]

merci mais je vx un exemple
on fais cette instruction en fonction
int fact(int n)

Code :

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

1
2
3
4
5
{
if (n==0) return 1;
else
return n*fact(n-1);
}

si on appel la fonction dans le main :

Code :

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

 fact(4);

quel sont les étape executer dans la pile ?

[Médinoc]

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

[millie]

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)

[Médinoc]

Tu sais, quatre octets ça fait 32 bits, pas 64...
PS: La factorielle dépasse la puissance de 2 à partir de n=4.

[millie]

Tu sais, quatre octets ça fait 32 bits, pas 64...

Ah oui, quel nase , trop d'architecture 64 bits tue le 32 bits

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

[yous18]

merci les amis pour votre aide