Initiation à l'algorithmique

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.

cours de récursivité

Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Professeur d'Informatique dans les CPGE

Cours Similaires :