Cours #4 - Récursivité et stack

[AlexMog]

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:
 

write - my_putchar - my_putstr - test.

 

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

[Azad]

Très bon tutoriel, c'est sympa que tu expliques pas à pas les différents points du C.
Peut-être un peu plus d'espace, sinon toujours pareil : Bien joué.

+1 point de rep.

[cegdd]

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.

 

J'ai compris a quoi ça sert de stocker ce qui est static dans une mémoire, mais pourquoi stocker les fonctions pour les supprimer par la suite ?

En quoi est-ce utile pour le programme ?

[AlexMog]

J'ai compris a quoi ça sert de stocker ce qui est static dans une mémoire, mais pourquoi stocker les fonctions pour les supprimer par la suite ?

En quoi est-ce utile pour le programme ?

En réalité, tout ce passe au niveau du code ASM.

Pour éviter de modifier la stack précédente, et être sûr que ladite stack ne soit pas modifiée, toutes les fonctions font une sauvegarde temporaire de la stack (c'est ce qu'on appelle le "generic push" en ASM).

La stack est donc remplie temporairement avec les anciennes valeurs.

Qui plus est, lorsque tu utilise une fonction qui contient elle même une variable, ou qui passe une variable en paramètre, celle-ci est stockée en stack (c'est pour cela qu'on préfèrera envoyer un pointeur plutôt qu'une structure en dur dans une fonctions ) (pour info: un pointeur = 8 octets (une structure contenant 2 int = 8 * 2 octets. Le choix est vite fait.)

[AlexMog]

Un exemple de code ASM avec un generic push:

;; exemple avec la fonction "hello world" x86 asm
global main
extern printf

section .text
main:
  push rbp ;; Ici, le generic push
  mov rbp, rsp ;; Suite du generic push (on le retrouvera dans toutes les fonctions en C (sans exceptions, il est ajouté automatiquement par le compilateur)

  mov rdi, FormatStr ;; 1er param de printf
  call printf ;; call de printf

  mov rsp, rbp ;; on remet l'ancienne stack en place
  pop rbp ;; on vire la sauvegarde de l'ancienne stack

  mov rax, 60 ;; on prépare l'appel au systcall "exit"
  xor rdi, rdi ;; on passe le paramètre 0 dans rdi (xor x, x revient à mettre 0 dans x (car un xor de 2 même valeurs donne 0)
  syscall ;; appel du systcall n°60
  ret

;; section read only
section .rodata
  FormatStr db 'Hello World !',0Ah,0

[cegdd]

ok merci =)