Les compilateurs peuvent-ils convertir la logique récursive en logique non récursive équivalente?

J'ai appris le F # et ça commence à influencer ma façon de penser quand je programme C #. À cette fin, j'ai utilisé la récursivité lorsque je pense que le résultat améliore la lisibilité et je ne peux pas imaginer qu'il se termine par un débordement de pile.

Cela m'amène à me demander si les compilateurs pourraient convertir automatiquement les fonctions récursives en une forme non récursive équivalente?

Oui, certains langages et compilateurs convertissent la logique récursive en logique non récursive. Ceci est connu comme l' optimisation des appels de queue - notez que tous les appels récursifs ne sont pas optimisés pour les appels de queue. Dans cette situation, le compilateur reconnaît une fonction du formulaire:

int foo(n) {
  ...
  return bar(n);
}

Ici, le langage est capable de reconnaître que le résultat renvoyé est le résultat d'une autre fonction et de changer un appel de fonction avec une nouvelle trame de pile en saut.

Sachez que la méthode factorielle classique:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

n'est pas un appel de queue optimisable en raison de l'inspection nécessaire au retour.

Pour rendre cet appel de queue optimisable,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Compiler ce code avec gcc -O2 -S fact.c(le -O2 est nécessaire pour activer l'optimisation dans le compilateur, mais avec plus d'optimisations de -O3, il devient difficile pour un humain de lire ...)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

On peut voir en segment .L4, le jneplutôt qu'un call(qui fait un appel de sous-programme avec un nouveau cadre de pile).

Veuillez noter que cela a été fait avec C. L'optimisation des appels de queue en java est difficile et dépend de l'implémentation de la JVM - tail-recursion + java et tail-recursion + optimisation sont de bons ensembles de balises à parcourir. Vous pouvez trouver d' autres langues JVM sont capables de récursion mieux optimiser la queue (essai de Clojure (qui nécessite l' RECUR d'optimiser la queue d'appel), ou scala).

Faites preuve de prudence.

La réponse est oui, mais pas toujours, et pas tous. C'est une technique qui porte plusieurs noms différents, mais vous pouvez trouver des informations assez définitives ici et sur wikipedia .

Je préfère le nom "Tail Call Optimization" mais il y en a d'autres et certaines personnes confondront le terme.

Cela dit, il y a quelques choses importantes à réaliser:

• Pour optimiser un appel de queue, l'appel de queue nécessite des paramètres qui sont connus au moment de l'appel. Cela signifie que si l'un des paramètres est un appel à la fonction elle-même, il ne peut pas être converti en boucle, car cela nécessiterait une imbrication arbitraire de ladite boucle qui ne peut pas être développée au moment de la compilation.

• C # n'optimise pas de manière fiable les appels de queue. L'IL a pour instruction de le faire que le compilateur F # émettra, mais le compilateur C # l'émettra de manière incohérente, et selon la situation JIT, le JIT peut ou non le faire du tout. Toutes les indications sont que vous ne devez pas compter sur l'optimisation de vos appels de queue en C #, le risque de débordement en le faisant est important et réel