Rémy m'a envoyé un petit lien que voici, qui explique comment il faudrait écrire un programme qui imprime 100 fois "Hello World" à l'écran, sans utiliser while, for ou do-while.

Cependant, je n'étais pas entièrement convaincu par l'approche récursive, et j'avais le sentiment que c'était moins optimal. Voici une traduction du pseudo-code proposé comme réponse :

#include <stdio.h>

void loop(int n) {
    if (n > 100)
        return;
    else
        printf("Hello World\n");

    loop(n + 1);
}

int main() {
    loop(1);
}

et voici ce que je propose :

#include <stdio.h>

int main() {

    int i = 0;

loop_start:
    printf("Hello World!\n");
    if (++i < 100) goto loop_start;

    return 0;
}   

Je sais ce que vous allez me dire, que goto c'est le diable incarné, tout ça tout ça. Mais comme je suis curieux de savoir comment le compilateur gèrerait les deux codes source, on peut se proposer de comparer les codes assembleur générés.

Pourquoi comparer ? Il est assez aisé d'imaginer qu'on risque d'allouer 100 trames dans la pile si on voulait exécuter la version récursive de cet algorithme, mais qu'on s'en passerait complètement avec la version goto. Mais peut-être que le problème disparaîtrait en expérimentant avec les niveaux d'optimisation de gcc.

J'ai compilé la version goto avec les flags -O0, -O1, -O2 et -O3 par simple curiosité pour ensuite passer un coup d'objdump dessus, et voir comment gcc optimiserait mon code. Voici la version non optimisée (-O0) :

080483c4 <main>:
 80483c4:       55                      push   %ebp
 80483c5:       89 e5                   mov    %esp,%ebp
 80483c7:       83 e4 f0                and    $0xfffffff0,%esp
 80483ca:       83 ec 20                sub    $0x20,%esp
 80483cd:       c7 44 24 1c 00 00 00    movl   $0x0,0x1c(%esp)
 80483d4:       00 
 80483d5:       eb 01                   jmp    80483d8 <main+0x14>
 80483d7:       90                      nop
 80483d8:       c7 04 24 c0 84 04 08    movl   $0x80484c0,(%esp)
 80483df:       e8 14 ff ff ff          call   80482f8 <puts@plt>
 80483e4:       83 44 24 1c 01          addl   $0x1,0x1c(%esp)
 80483e9:       83 7c 24 1c 63          cmpl   $0x63,0x1c(%esp)
 80483ee:       7e e7                   jle    80483d7 <main+0x13>
 80483f0:       b8 00 00 00 00          mov    $0x0,%eax
 80483f5:       c9                      leave  
 80483f6:       c3                      ret    

Là, à l'adresse 0x80483cd, le movl correspond à l'initialisation de ma variable locale i. Pourtant, un registre aurait très bien fait l'affaire. Avec -O1, on voit que gcc attribue le registre %ebx à ma variable i:

080483c4 <main>:
 80483c4:       55                      push   %ebp
 80483c5:       89 e5                   mov    %esp,%ebp
 80483c7:       83 e4 f0                and    $0xfffffff0,%esp
 80483ca:       53                      push   %ebx
 80483cb:       83 ec 1c                sub    $0x1c,%esp
 80483ce:       bb 00 00 00 00          mov    $0x0,%ebx
 80483d3:       c7 04 24 c0 84 04 08    movl   $0x80484c0,(%esp)
 80483da:       e8 19 ff ff ff          call   80482f8 <puts@plt>
 80483df:       83 c3 01                add    $0x1,%ebx
 80483e2:       83 fb 64                cmp    $0x64,%ebx
 80483e5:       75 ec                   jne    80483d3 <main+0xf>
 80483e7:       b8 00 00 00 00          mov    $0x0,%eax
 80483ec:       83 c4 1c                add    $0x1c,%esp
 80483ef:       5b                      pop    %ebx
 80483f0:       89 ec                   mov    %ebp,%esp
 80483f2:       5d                      pop    %ebp
 80483f3:       c3                      ret

Par contre, l'instruction mov $0x0,%ebx aurait pu être remplacée par xor %ebx, %ebx, ce qui fait la même chose en prenant moins de place et en plus rapide. C'est d'ailleurs une technique utilisée dans des shellcodes pour initialiser un registre à zéro en évitant d'introduire des octets nuls dans le code. Avec -O2, c'est effectivement ce qui se passe :

080483d0 <main>:
 80483d0:       55                      push   %ebp
 80483d1:       89 e5                   mov    %esp,%ebp
 80483d3:       83 e4 f0                and    $0xfffffff0,%esp
 80483d6:       53                      push   %ebx
 80483d7:       31 db                   xor    %ebx,%ebx
 80483d9:       83 ec 1c                sub    $0x1c,%esp
 80483dc:       8d 74 26 00             lea    0x0(%esi,%eiz,1),%esi
 80483e0:       83 c3 01                add    $0x1,%ebx
 80483e3:       c7 04 24 c0 84 04 08    movl   $0x80484c0,(%esp)
 80483ea:       e8 09 ff ff ff          call   80482f8 <puts@plt>
 80483ef:       83 fb 64                cmp    $0x64,%ebx
 80483f2:       75 ec                   jne    80483e0 <main+0x10>
 80483f4:       83 c4 1c                add    $0x1c,%esp
 80483f7:       31 c0                   xor    %eax,%eax
 80483f9:       5b                      pop    %ebx
 80483fa:       89 ec                   mov    %ebp,%esp
 80483fc:       5d                      pop    %ebp
 80483fd:       c3                      ret

Remarquez le fameux xor. Avec -O3, cependant, il n'y a aucune différence avec -O2.

Essayons maintenant avec la version récursive de cet algorithme. Voici le code avec -O0 :

080483c4 <loop>:
 80483c4:       55                      push   %ebp
 80483c5:       89 e5                   mov    %esp,%ebp
 80483c7:       83 ec 18                sub    $0x18,%esp
 80483ca:       83 7d 08 64             cmpl   $0x64,0x8(%ebp)
 80483ce:       7f 1c                   jg     80483ec <loop+0x28>
 80483d0:       c7 04 24 d0 84 04 08    movl   $0x80484d0,(%esp)
 80483d7:       e8 1c ff ff ff          call   80482f8 <puts@plt>
 80483dc:       8b 45 08                mov    0x8(%ebp),%eax
 80483df:       83 c0 01                add    $0x1,%eax
 80483e2:       89 04 24                mov    %eax,(%esp)
 80483e5:       e8 da ff ff ff          call   80483c4 <loop>
 80483ea:       eb 01                   jmp    80483ed <loop+0x29>
 80483ec:       90                      nop
 80483ed:       c9                      leave  
 80483ee:       c3                      ret    

080483ef <main>:
 80483ef:       55                      push   %ebp
 80483f0:       89 e5                   mov    %esp,%ebp
 80483f2:       83 e4 f0                and    $0xfffffff0,%esp
 80483f5:       83 ec 10                sub    $0x10,%esp
 80483f8:       c7 04 24 01 00 00 00    movl   $0x1,(%esp)
 80483ff:       e8 c0 ff ff ff          call   80483c4 <loop>
 8048404:       c9                      leave  
 8048405:       c3                      ret

et avec -O2 (en ne montrant que la fonction loop) :

080483d0 <loop>:
 80483d0:       55                      push   %ebp
 80483d1:       89 e5                   mov    %esp,%ebp
 80483d3:       53                      push   %ebx
 80483d4:       83 ec 14                sub    $0x14,%esp
 80483d7:       8b 5d 08                mov    0x8(%ebp),%ebx
 80483da:       83 fb 64                cmp    $0x64,%ebx
 80483dd:       7f 15                   jg     80483f4 <loop+0x24>
 80483df:       90                      nop
 80483e0:       83 c3 01                add    $0x1,%ebx
 80483e3:       c7 04 24 e0 84 04 08    movl   $0x80484e0,(%esp)
 80483ea:       e8 09 ff ff ff          call   80482f8 <puts@plt>
 80483ef:       83 fb 64                cmp    $0x64,%ebx
 80483f2:       7e ec                   jle    80483e0 <loop+0x10>
 80483f4:       83 c4 14                add    $0x14,%esp
 80483f7:       5b                      pop    %ebx
 80483f8:       5d                      pop    %ebp
 80483f9:       c3                      ret    
 80483fa:       8d b6 00 00 00 00       lea    0x0(%esi),%esi

Pour ceux que ça gave de lire de l'assembleur : avec -O0, le code assembleur appelle de manière stupide lui-même 100 fois avec call, ce qui fait aussi 100 créations et destructions de trames de pile. Imaginez si nous avions des millions d'appels récursifs ! Sans parler du fait qu'aucun registre n'est alloué pour les variables locales, alors qu'on n'en a qu'une seule dans notre fonction et qu'elle aurait pu être dans %ebx. Cependant, avec -O2, gcc fait ce qu'on appelle une optimisation des appels terminaux. En effet, nous avons ici affaire à une récursion terminale, ce qui permet d'en faire un code optimisé qui ressemble pas mal à ma version goto avec -O2. Trop fort, gcc !

Bref, en conclusion, la version récursive n'est pas si mauvaise que ça, contrairement à ce que je pensais ; cependant, il faut absolument compiler avec -O2 pour que ce soit réellement intéressant. Mais je souhaite quand même en finir avec la diabolisation systématique du goto qui, lorsqu'il est bien utilisé, peut rendre le code bien plus lisible. Par exemple, pour sortir d'un switch et sortir du while qui le contient sans goto, il faudrait y aller à coups de booléens susceptibles de rendre les conditions de sortie des while en question plus compliqués, et ce juste pour un cas particulier. C'est pourquoi, et plus particulièrement en programmation système, je tiens à garder ce mot-clé dans mon arsenal.

En tout cas, c'est clair qu'on pouvait s'affranchir de goto dans notre exemple (d'ailleurs, c'est pour ça qu'on a des structures de contrôle comme for ou while). Mais regarder comment gcc optimise ce genre de programmes à chaque fois reste une expérience intéressante.