Comment implémenter efficacement la récursivité en Python

Comprendre la récursion en Python

La récursion est une technique de programmation où une fonction s'appelle pour résoudre un problème. Dans cet article, nous nous concentrerons sur l'implémentation de la récursivité en Python pour trouver la somme des entiers dans une liste, ainsi que sur d'autres applications récursives courantes.

Liste de la somme à l'aide de la récursion

Supposons que nous ayons un fonction, listSum, qui prend une liste d'entiers et renvoie leur somme. Voici son implémentation récursive de base :

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

    # Recursive call with the rest of the list
    return ls[0] + listSum(ls[1:])</code>

Récursion d'appel de queue

Pour optimiser la récursion ci-dessus, nous pouvons utiliser la récursion d'appel de queue. Cela implique de transmettre le résultat courant ainsi que la liste à l'appel récursif :

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

Passing Around Index

Pour éviter de créer des listes intermédiaires, nous pouvons passer l'index de l'élément courant au appel récursif :

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

Version de la fonction interne

Si vous préférez une approche plus encapsulée, vous pouvez définir une fonction interne dans listSum pour gérer la logique récursive :

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

Paramètres par défaut

Pour plus de commodité, vous pouvez utiliser les paramètres par défaut pour simplifier l'appel de fonction :

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

Problème de puissance récursive

La récursion peut également être appliquée pour calculer les puissances . Considérez la fonction de puissance qui prend une base et un exposant :

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

Puissance optimisée des appels de queue

Pour optimiser la puissance à l'aide de la récursion des appels de queue :

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