Rechercher dans la communauté
Affichage des résultats pour les étiquettes 'stack'.
1 résultat trouvé
-
Bonjour à tous, Nous passons encore à un autre niveau aujourd'hui, et nous allons voir ensemble la Récursivité, et la notion de Stack. I- La récursivité, c'est quoi? La récursivité, c'est un autre moyen de provoquer une "boucle" dans une fonction. C'est totalement différent de ce que je vous ai expliqué avant. Nous avions vu la partie "itérative" du C, qui corresponds à exécuter un programme, ligne par ligne. Ici, nous allons apprendre un peux plus les fonctions de la récursivité, et comment elle réagit sur la stack. C'est une façon de faire, pour qu'une fonction se rappelle elle-même. Prenons l'exemple suivant: int test(int a) { a++; if (a < 12) test(a); return (a); } int main(void) { my_putnbr(test(1));// my_putnbr est une fonction permettant d'afficher une valeur numérique. Vous devez la re-créer ou utiliser printf (ce qui est interdit par la norme! Re-créez la, ça vous apprendra pas mal de choses!) } La fonction "test" est ici récursive. Ce code nous affichera: 12 Vous l'aurez compris, la récursivité peut être utile dans plusieurs cas (pour annecdote, my_putnbr peut être codé en 3 lignes avec de la récursivité). Les fonctions récursives peuvent êtres comparées à des poupées russes s'emboitant. Ne vous perdez pas! Et ne vous inquiétez pas! Je vais mieux vous l'expliquer en vous expliquant le fonctionnement de la stack. II- La stack? DAFUQ? Je vais pouvoir vous expliquer une notion qui est assez floue dans le cerveau de beaucoup de développeurs: la stack. La stack est une mémoire assignée à votre programme pour la prise en charge de tout ce qui est "static" dans votre programme (d'où le nom "stack"). Lors du lancement de votre programme, la stack est vide. Si vous appelez la fonction "test" celle-ci va se rajouter dans la stack. Si, de la fonction "test", vous appelez la fonction "my_putstr" celle-ci va se rajouter dans la stack, de même pour la fonction "my_putchar" contenue dans la fonction "my_putstr" qui fera elle-même appel à la fonction "write" qui se rajoutera à son tour à la stack. La stack a donc constitué une liste d'exécution. On peut re-définir l'ordre d'exécution précédent comme ceci: Il ne faut pas oublier que la stack est une mémoire, et qu'elle va stocker tout ce qui est statique dans notre programme. Donc, si nous la sur-utilisons (une boucle infinie de fonctions par exemple: surempiler les poupées russes), nous risquons de faire segfault (segmentation fault) notre programme (C'est souvent une explication pour les programme qui segfault sans raisons). Lorsqu'une fonction finit son exécution, elle est supprimée de la stack. Pour vous faire un schéma, imaginez un tas de vaisselle: à chaque fois, vous rajoutez une assiette sale sur le tat, et lorsque vous faites la vaiselle, vous enlevez vos assiettes dans l'ordre contraire de celui de l'empilation. Reprenons la théorie: Une fonction récursive est une fonction qui se rappelle elle-même. Elle se rajoute donc sur la stack, puis se rappelle. Elle se rajoute donc encore une fois sur la stack, puis se rappelle...etc... Et là, deux choses peuvent avoir lieu: Soit on atteint la taille maximum de la stack (définie par le système), et on provoque un segfault, sinon, et c'est ce que vous devrez faire la plupart du temps en utilisant les récursifs, vous devez prévoir une condition d'arrêt du rappel de cette fonction, donc à un moment de votre récursivité, vous dites STOP, cette fois je ne me rappelle pas, car mon rôle est terminé. A ce moment là, vous allez libérer la stack de toutes les fonctions que vous avez au préalable ajouté. Le mieux, reste encore de vous montrer un exemple de ce qu'il ne faut pas faire: Créons un programme qui va afficher "hello" indéfiniment: void my_putchar(char c) { write(1, &c, 1); } void fg() { my_putchar('h'); my_putchar('e'); my_putchar('l'); my_putchar('l'); my_putchar('o'); my_putchar('\n'); fg(); } int main(void) { fg(); } Effectivement, on voit "hello" s'afficher plusieurs fois, mais si on laisse tourner notre programme jusqu'à ce que la stack soit remplie, on remarque de notre programme crash, et qu'un segfault est apparu. C'est l'exemple typique de ce que l'on peut attendre au niveau des problèmes liés à la récursivité. Un autre exemple, c'est notre légendaire my_putnbr: void my_put_nbr(int nb) { if (nb <= 9 && nb >= 0) my_putchar(nb + '0'); else { my_put_nbr(nb / 10); my_put_nbr(nb % 10); } } c'est typiquement la bonne utilisation de la récursivité. Voilà, j'espère vous avoir encore aidé au niveau de votre apprentissage avancé du C. Rendez-vous au prochain cours! Cours écrit par AlexMog. Contact: alexmog [at] live [point] fr