récursivité terminale
Qu'est ce qu'une récursion terminale ?
Une fonction récursive est terminale lorsque l'appel récursif est la dernière chose exécutée par la fonction.
Par exemple, la fonction somme qui calcule la somme de 0 à x
fonction somme(x,res)
SI x=0 ALORS
retourner res
retourner somme(x-1,x+res)
def somme(x,res):
if x == 0:
return res
return somme(x-1, x+res)
print(somme(3, 0))
Les fonctions récursives terminales est considérées comme meilleures que les fonctions non terminales puisqu'une récursion terminale peut être optimisé par le compilateur.
L'idée utilisée par les compilateurs pour optimiser les fonctions récursives est simple, puisque l'appel récursif est la dernière instruction, il n'y a plus rien à faire dans la fonction courante, donc sauvegarder le cadre de la pile de la fonction courante n'est d'aucune utilité.
Une fonction récursive non-terminale peut-elle être écrite comme terminale pour l'optimiser?
Considérons la fonction suivante pour calculer la factorielle de N.
C'est une fonction récursive non-terminale. Bien qu'il ressemble à une fonction récursive terminale à première vue. Si on regarde de plus près, nous pouvons voir que la valeur retournée par factorielle(n-1) est utilisée dans factorielle(n), de sorte que l'appel de factorielle(n-1) n'est pas la dernière chose à faire par factorielle(n)
fonction factorielle(n)
SI n=1 ALORS
retourner 1
retourner n*factorielle(n-1)
def factorielle(n):
if n == 1:
return 1
return (n * factorielle(n-1))
La fonction ci-dessus peut être écrite comme une fonction récursive terminale. L'idée est d'utiliser un argument de plus et d'accumuler la valeur factorielle dans le second argument. Lorsque n atteint 1, retournez la valeur accumulée.
fonction factorielle(n, val)
SI n=1 ALORS
retourner val
retourner factorielle(n-1, n * val)
def factorielle(n, val):
if n == 1:
return val
return factorielle(n-1, n * val)
Élimination de L'appel terminale ?
la récursive terminale est meilleure que la récursion non-terminale car elle peut être optimisée par les compilateurs modernes.
Le compilateur moderne élimine les appels terminales pour optimiser le code du récursion terminale.
Si nous examinons de plus près la fonction ci-dessus, nous pouvons supprimer le dernier appel avec goto (C/C++).
void factorielle(n){
f=1
start:
if(n==1) return f
f=f*n
n=n-1
goto start
}Par conséquent, la tâche des compilateurs est d'identifier la récursion terminale, d'ajouter une étiquette au début et de mettre à jour les paramètres à la fin, puis d'ajouter la dernière instruction goto.
Élimination de L'appel terminale en python
Python ne prend pas en charge l'optimisation d'appels terminales. Il y a plusieurs raisons à cela, la plus simple étant que python est construit autour de l'idée d'itération plus que la récursion.
