Comment implémenter la récursion des appels de queue pour une sommation efficace en Python ?

Récursion en Python : un guide pour comprendre

Fonction récursive pour additionner une liste d'entiers

Supposons que nous devions créer une fonction récursive appelée "listSum" qui calcule la somme de tous les entiers d'une liste. Le but est de le faire sans utiliser de fonctions intégrées. Tout d'abord, nous devons réfléchir à la manière dont nous pouvons exprimer le résultat de la fonction en fonction d'elle-même.

Dans ce cas, nous pouvons obtenir le résultat en ajoutant le premier nombre au résultat de l'appel de la même fonction avec le reste des éléments de la liste. De manière récursive, cela peut s'exprimer comme :

listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6])
                         = 1 + (3 + listSum([4, 5, 6]))
                         = 1 + (3 + (4 + listSum([5, 6])))
                         = 1 + (3 + (4 + (5 + listSum([6]))))
                         = 1 + (3 + (4 + (5 + (6 + listSum([])))))

Le cas de base de la récursion est lorsque la liste devient vide, un événement nécessitant un résultat de 0. Implémentation de cette approche dans le code Python :

<code class="python">def listSum(ls):
    if not ls:
        return 0
    return ls[0] + listSum(ls[1:])</code>

Récursion d'appel de queue

L'implémentation précédente dépend de la valeur de l'appel de fonction précédent pour calculer le résultat réel. Cela peut être amélioré en utilisant Tail Call Recursion :

<code class="python">def listSum(ls, result):
    if not ls:
        return result
    return listSum(ls[1:], result + ls[0])</code>

En introduisant un résultat de paramètre supplémentaire, nous y accumulons la somme et la renvoyons lorsque la condition de base est remplie.

Passing Around Index

Pour éviter de créer plusieurs listes intermédiaires, on peut faire circuler l'index de l'élément à traiter :

<code class="python">def listSum(ls, index, result):
    if index == len(ls):
        return result
    return listSum(ls, index + 1, result + ls[index])</code>

La condition de base vérifie si l'index a atteint la longueur de la liste.

Version de la fonction interne

Pour simplifier le passage des paramètres, nous pouvons utiliser une fonction interne :

<code class="python">def listSum(ls):
    def recursion(index, result):
        if index == len(ls):
            return result
        return recursion(index + 1, result + ls[index])
    return recursion(0, 0)</code>

La récursion de la fonction interne accepte les paramètres d'index et de résultat, et listSum renvoie le résultat de l'appel de la fonction interne avec des valeurs initiales.

Version des paramètres par défaut

L'utilisation des paramètres par défaut est une simplification supplémentaire :

<code class="python">def listSum(ls, index=0, result=0):
    if index == len(ls):
        return result
    return listSum(ls, index + 1, result + ls[index])</code>

Les valeurs par défaut sont attribuées à l'index et résultat s'il n'est pas explicitement spécifié par l'appelant.

Problème de puissance récursive

Considérez le problème du calcul de la puissance (base, exposant), qui renvoie la valeur de la base élevée à la puissance de l'exposant. De manière récursive, nous pouvons définir la solution :

power(2, 5) = 2 * power(2, 4)
            = 2 * (2 * power(2, 3))
            = 2 * (2 * (2 * power(2, 2)))
            = 2 * (2 * (2 * (2 * power(2, 1))))

La condition de base est lorsque l'exposant devient 1 ou moins, auquel cas le résultat est la base elle-même :

            = 2 * (2 * (2 * (2 * 2)))
            = 2 * (2 * (2 * 4))
            = 2 * (2 * 8)
            = 2 * 16
            = 32

Implémentation en Python :

<code class="python">def power(base, exponent):
    if exponent <= 1:
        return base
    return base * power(base, exponent - 1)</code>

Utilisation des paramètres par défaut pour la version Tail Call Optimized :

<code class="python">def power(base, exponent, result=1):
    if exponent <= 0:
        return result
    return power(base, exponent - 1, result * base)</code>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!