Comment calculer récursivement la somme des éléments dans une liste en Python ?

Bases de la récursion en Python

La récursion est une technique puissante en informatique où une fonction s'appelle pour résoudre un problème. Dans ce contexte, nous abordons la question du développement d'une fonction Python récursive appelée "listSum" pour déterminer la somme de tous les entiers d'une liste donnée.

Considérez le problème : "Écrivez une fonction récursive, 'listSum,' qui prend une liste d'entiers et renvoie la somme de tous les entiers de la liste. "

Compréhension conceptuelle

Comprendre comment résoudre ce problème de manière récursive implique d'exprimer la solution en termes de fonction elle-même. Dans ce scénario, le résultat peut être obtenu en ajoutant le premier nombre au résultat de l'application de la même fonction aux éléments restants de la liste. Par exemple :

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

Dans cet exemple, la condition de base est listSum([]), qui représente une liste vide. Puisqu'une liste vide n'a aucun élément à additionner, son résultat est 0.

Implémentation de listSum

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

Dans cette implémentation, nous vérifions une liste vide comme condition de base et renvoyons 0. Pour les listes avec des éléments, nous ajoutons le premier élément au résultat récursif des éléments restants.

Récursion d'appel de queue

Pour l'optimisation, nous pouvons éviter de nous fier à la valeur de retour de l'appel récursif précédent . Passer le résultat en paramètre nous permet de renvoyer immédiatement la valeur lorsque la condition de base est remplie :

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

Cette version accumule effectivement la somme dans le paramètre 'result' et la renvoie lorsque la condition de base est remplie .

Passing Around Index

Pour éviter de créer des listes intermédiaires, on peut passer l'index de l'élément courant :

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

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

Version de la fonction interne

Pour simplifier la gestion des paramètres, nous pouvons créer une fonction interne pour gérer la récursion :

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

Version des paramètres par défaut

Pour plus de simplicité, nous pouvons utiliser les paramètres par défaut :

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

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!