Comment implémenter des fonctions récursives pour additionner les éléments de liste et calculer les puissances ?

Fonction récursive pour additionner les éléments d'une liste

La tâche à accomplir consiste à créer une fonction Python, bien nommée "listSum", qui peut calculer la somme de tous les entiers d’une liste donnée. Bien qu'elle n'utilise pas de fonctions intégrées, la fonction doit adopter une approche récursive.

Comprendre la stratégie récursive

Pour saisir l'essence de la récursion, il est essentiel de formuler le résultat de la fonction en utilisant la fonction elle-même. Dans ce cas, nous pouvons obtenir le résultat souhaité en combinant le premier nombre avec le résultat obtenu en appliquant la même fonction aux éléments restants de la liste.

Par exemple, considérons la liste [1, 3, 4, 5 , 6] :

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([])))))

La fonction arrête sa récursion lorsque la liste d'entrée devient vide, auquel cas la somme est nulle. Ceci est connu comme la condition de base de la récursion.

Implémentation récursive simple

La version simple de notre fonction récursive ressemble à ceci :

<code class="python">def listSum(ls):
    # Base condition
    if not ls:
        return 0

    # First element + result of calling 'listsum' with rest of the elements
    return ls[0] + listSum(ls[1:])</code>

Cette approche s'appelle récursivement jusqu'à ce que la liste soit vide, renvoyant finalement la somme totale.

Récursion d'appel de queue

Une forme optimisée de récursion, connue sous le nom d'appel de queue optimisation, peut être utilisée pour améliorer l’efficacité de la fonction. Dans cette variante, l'instruction return s'appuie directement sur le résultat de l'appel récursif, éliminant ainsi le besoin d'appels de fonction intermédiaires.

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

Ici, la fonction prend un paramètre supplémentaire, 'result', qui représente le somme accumulée jusqu’à présent. La condition de base renvoie « résultat », tandis que l'appel récursif transmet le « résultat » avec l'élément suivant dans la liste.

Récursion à index glissant

Pour des raisons d'efficacité , nous pouvons éviter de créer des listes intermédiaires superflues en employant un index glissant qui suit l'élément à traiter. Cela modifie également la condition de base.

<code class="python">def listSum(ls, index, result):
    # Base condition
    if index == len(ls):
        return result

    # Call with next index and add the current element to result
    return listSum(ls, index + 1, result + ls[index])</code>

Récursion de fonction imbriquée

Pour améliorer la lisibilité du code, nous pouvons imbriquer la logique récursive dans une fonction interne, en conservant la principale fonction seule responsable de la transmission des arguments.

<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>

Récursion des paramètres par défaut

L'utilisation des paramètres par défaut fournit une approche simplifiée pour gérer les arguments de la fonction.

<code class="python">def listSum(ls, index=0, result=0):
    # Base condition
    if index == len(ls):
        return result

    # Call with next index and add the current element to result
    return listSum(ls, index + 1, result + ls[index])</code>

Dans ce cas, si l'appelant omet les arguments, les valeurs par défaut de 0 pour « index » et « résultat » seront utilisées.

Fonction de puissance récursive

En appliquant les concepts de récursivité, nous pouvons concevoir une fonction qui calcule l'exponentiation d'un nombre donné.

<code class="python">def power(base, exponent):
    # Base condition, if 'exponent' is lesser than or equal to 1, return 'base'
    if exponent <= 1:
        return base

    return base * power(base, exponent - 1)</code>

De même, nous pouvons implémenter une version optimisée pour les appels de queue :

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([])))))

Cette version réduit la valeur de l'exposant dans chaque appel récursif et multiplie le « résultat » par « base », renvoyant finalement le résultat souhaité.

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!