Python Language
Récursivité

Remarques

Somme des nombres de 1 à n

Si je voulais trouver la somme des nombres de 1 à n où n est un nombre naturel, je peux faire 1 + 2 + 3 + 4 + ... + (several hours later) + n . Sinon, je pourrais écrire une boucle for :

n = 0
for i in range (1, n+1):
    n += i

Ou je pourrais utiliser une technique connue sous le nom de récursivité:

def recursion(n):
    if n == 1:
        return 1
    return n + recursion(n - 1)

La récursivité présente des avantages par rapport aux deux méthodes ci-dessus. La récursion prend moins de temps que l'écriture de 1 + 2 + 3 pour une somme de 1 à 3. Pour la recursion(4) , la récursion peut être utilisée pour reculer:

Appels de fonction: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)

Alors que la boucle for fonctionne strictement en avant: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). Parfois, la solution récursive est plus simple que la solution itérative. Cela est évident lors de la mise en œuvre d'une inversion d'une liste chaînée.

Le quoi, comment et quand de récursivité

La récursivité se produit lorsqu'un appel de fonction provoque l'appel de la même fonction avant la fin de l'appel de fonction d'origine. Par exemple, considérons l’expression mathématique bien connue x! (c'est-à-dire l'opération factorielle). L'opération factorielle est définie pour tous les entiers non négatifs comme suit:

• Si le nombre est 0, la réponse est 1.
• Sinon, la réponse est ce nombre multiplié par la factorielle de moins d’un chiffre.

En Python, une implémentation naïve de l'opération factorielle peut être définie comme une fonction comme suit:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Les fonctions de récursion peuvent être difficiles à saisir parfois, alors parcourons cette étape par étape. Considérons l'expression factorial(3) . Ceci et tous les appels de fonctions créent un nouvel environnement . Un environnement est simplement une table qui mappe les identifiants (par exemple, n , factorial , print , etc.) à leurs valeurs correspondantes. À tout moment, vous pouvez accéder à l'environnement actuel en utilisant les utilisateurs locals() . Dans le premier appel de fonction, la seule variable locale définie est n = 3 . Par conséquent, imprimer les locals() afficherait {'n': 3} . Puisque n == 3 , la valeur de retour devient n * factorial(n - 1) .

À cette étape suivante, les choses peuvent devenir un peu confuses. En regardant notre nouvelle expression, nous savons déjà ce que n est. Cependant, nous ne savons pas encore quelle factorial(n - 1) est. Tout d'abord, n - 1 évalué à 2 . Ensuite, 2 est passé à factorial comme valeur pour n . Puisqu'il s'agit d'un nouvel appel de fonction, un deuxième environnement est créé pour stocker ce nouveau n . Soit A le premier environnement et B le deuxième environnement. Un existe toujours et est égal à {'n': 3} , cependant, B (qui est égal à {'n': 2} ) est l'environnement actuel. En regardant le corps de la fonction, la valeur de retour est, encore une fois, n * factorial(n - 1) . Sans évaluer cette expression, substituons-la à l'expression de retour d'origine. En faisant cela, nous mentalement rejeter B, alors pensez à remplacer n en conséquence (ie les références à B « s n sont remplacés par n - 1 qui utilise un » s n ). Maintenant, l'expression de retour d'origine devient n * ((n - 1) * factorial((n - 1) - 1)) . Prenez une seconde pour vous assurer que vous comprenez pourquoi.

Maintenant, évaluons la partie factorial((n - 1) - 1)) de celle-ci. Puisque A est n == 3 , nous passons 1 en factorial . Par conséquent, nous créons un nouvel environnement C qui est égal à {'n': 1} . Là encore, la valeur de retour est n * factorial(n - 1) . Alors, remplaçons factorial((n - 1) - 1)) de l'expression de retour «original» de la même manière que nous avons ajusté l'expression de retour d'origine plus tôt. L'expression «originale» est maintenant n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) .

Presque fini. Maintenant, nous devons évaluer factorial((n - 2) - 1) . Cette fois, nous passons à 0 . Par conséquent, cela évalue à 1 . Maintenant, effectuons notre dernière substitution. L'expression de retour «originale» est maintenant n * ((n - 1) * ((n - 2) * 1)) . Rappelant que l'expression de retour d'origine est évaluée sous A , l'expression devient 3 * ((3 - 1) * ((3 - 2) * 1)) . Cela, bien sûr, évalue à 6. Pour confirmer que c'est la bonne réponse, rappelez-vous que 3! == 3 * 2 * 1 == 6 . Avant de poursuivre la lecture, assurez-vous de bien comprendre le concept d’environnement et son application à la récursivité.

L'instruction if n == 0: return 1 s'appelle un cas de base. En effet, il ne présente aucune récursivité. Un cas de base est absolument nécessaire. Sans celui-ci, vous rencontrerez une récursion infinie. Cela dit, tant que vous avez au moins un cas de base, vous pouvez avoir autant de cas que vous le souhaitez. Par exemple, nous pourrions avoir une factorial écrite de la manière suivante:

def factorial(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return n * factorial(n - 1)

Vous pouvez également avoir plusieurs cas de récursivité, mais nous n'entrerons pas dans cette perspective, car elle est relativement rare et souvent difficile à traiter mentalement.

Vous pouvez également avoir des appels de fonction récursifs «parallèles». Par exemple, considérons la séquence de Fibonacci qui est définie comme suit:

• Si le nombre est 0, la réponse est 0.
• Si le nombre est 1, la réponse est 1.
• Sinon, la réponse est la somme des deux nombres précédents de Fibonacci.

Nous pouvons définir cela comme suit:

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n - 2) + fib(n - 1)

Je ne vais pas parcourir cette fonction aussi complètement que je l'ai fait avec factorial(3) , mais la valeur de retour finale de fib(5) est équivalente à l'expression suivante ( syntaxiquement invalide):

(
  fib((n - 2) - 2)
  +
  (
    fib(((n - 2) - 1) - 2)
    +
    fib(((n - 2) - 1) - 1)
  )
)
+
(
  (
    fib(((n - 1) - 2) - 2)
    +
    fib(((n - 1) - 2) - 1)
  )
  +
  (
    fib(((n - 1) - 1) - 2)
    +
    (
      fib((((n - 1) - 1) - 1) - 2)
      +
      fib((((n - 1) - 1) - 1) - 1)
    )
  )
)

Cela devient (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) qui bien sûr est évalué à 5 .

Passons maintenant à quelques termes de vocabulaire supplémentaires:

• Un appel de fin est simplement un appel de fonction récursif qui est la dernière opération à effectuer avant de renvoyer une valeur. Pour être clair, return foo(n - 1) est un appel de fin, mais return foo(n - 1) + 1 ne l’est pas (puisque l’ajout est la dernière opération).
• L'optimisation des appels de queue (TCO) est un moyen de réduire automatiquement la récursivité dans les fonctions récursives.
• L'élimination des appels de queue (TCE) est la réduction d'un appel de fin à une expression qui peut être évaluée sans récurrence. Le TCE est un type de TCO.

L'optimisation des appels de queue est utile pour plusieurs raisons:

• L'interpréteur peut minimiser la quantité de mémoire occupée par les environnements. Comme aucun ordinateur ne dispose d'une mémoire illimitée, des appels de fonction récursifs excessifs entraîneraient un débordement de pile .
• L'interpréteur peut réduire le nombre de commutateurs de trames de pile .

Python n'a aucune forme de TCO implémentée pour plusieurs raisons . Par conséquent, d'autres techniques sont nécessaires pour contourner cette limitation. La méthode de choix dépend du cas d'utilisation. Avec une certaine intuition, les définitions de factorial et de fib peuvent être facilement converties en code itératif comme suit:

def factorial(n):
    product = 1
    while n > 1:
        product *= n
        n -= 1
    return product

def fib(n):
    a, b = 0, 1
    while n > 0:
        a, b = b, a + b
        n -= 1
    return a

C'est généralement le moyen le plus efficace d'éliminer manuellement la récursivité, mais cela peut devenir assez difficile pour des fonctions plus complexes.

Un autre outil utile est le décorateur lru_cache de Python, qui permet de réduire le nombre de calculs redondants.

Vous avez maintenant une idée de comment éviter la récursivité en Python, mais quand devriez- vous utiliser la récursivité? La réponse est «pas souvent». Toutes les fonctions récursives peuvent être implémentées de manière itérative. Il suffit simplement de trouver comment le faire. Cependant, il existe de rares cas de récursivité. La récursivité est courante en Python lorsque les entrées attendues ne provoqueraient pas un nombre significatif d'appels de fonction récursifs.

Si la récursivité est un sujet qui vous intéresse, je vous implore d'étudier des langages fonctionnels tels que Scheme ou Haskell. Dans ces langues, la récursivité est beaucoup plus utile.

Veuillez noter que l'exemple ci-dessus pour la séquence Fibonacci, bien qu'il montre comment appliquer la définition en python et l'utilisation ultérieure du cache lru, a un temps d'exécution inefficace car il effectue 2 appels récursifs pour chaque cas non-base. Le nombre d'appels à la fonction augmente exponentiellement à n .
Plutôt non intuitivement, une implémentation plus efficace utiliserait la récursivité linéaire:

def fib(n):
    if n <= 1:
        return (n,0)
    else:
        (a, b) = fib(n - 1)
        return (a + b, a)

Mais celui-là a le problème de retourner une paire de chiffres. Cela souligne que certaines fonctions ne gagnent pas beaucoup de récursivité.

Exploration d'arbres avec récursion

Disons que nous avons l'arbre suivant:

root
- A
  - AA
  - AB
- B
  - BA
  - BB
    - BBA

Maintenant, si nous souhaitons énumérer tous les noms des éléments, nous pourrions le faire avec un simple for-loop. Nous supposons qu'il y a une fonction get_name() pour retourner une chaîne du nom d'un noeud, une fonction get_children() pour renvoyer une liste de tous les sous-noeuds d'un noeud donné dans l'arborescence et une fonction get_root() pour obtenir le noeud racine.

root = get_root(tree)
for node in get_children(root):
    print(get_name(node))
    for child in get_children(node):
        print(get_name(child))
        for grand_child in get_children(child):
            print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA

Cela fonctionne bien et rapidement, mais que se passe-t-il si les sous-nœuds ont leurs propres sous-nœuds? Et ces sous-noeuds pourraient avoir plus de sous-noeuds ... Et si vous ne savez pas à l'avance combien il y en aura? Une méthode pour résoudre ce problème est l'utilisation de la récursivité.

def list_tree_names(node):
    for child in get_children(node):
        print(get_name(child))
        list_tree_names(node=child)

list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA

Vous souhaitez peut-être ne pas imprimer, mais renvoyer une liste plate de tous les noms de nœuds. Cela peut être fait en passant une liste déroulante en paramètre.

def list_tree_names(node, lst=[]):
    for child in get_children(node):
        lst.append(get_name(child))
        list_tree_names(node=child, lst=lst)
    return lst

list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']

Augmenter la profondeur de récursivité maximale

Il y a une limite à la profondeur de la récursion possible, qui dépend de l'implémentation de Python. Lorsque la limite est atteinte, une exception RuntimeError est déclenchée:

RuntimeError: Maximum Recursion Depth Exceeded

Voici un exemple de programme qui provoquerait cette erreur:

def cursing(depth):
  try:
    cursing(depth + 1) # actually, re-cursing
  except RuntimeError as RE:
    print('I recursed {} times!'.format(depth))
cursing(0)
# Out: I recursed 1083 times!

Il est possible de modifier la limite de profondeur de récursion en utilisant

sys.setrecursionlimit(limit) 

Vous pouvez vérifier quels sont les paramètres actuels de la limite en exécutant:

sys.getrecursionlimit()

Utiliser la même méthode ci-dessus avec notre nouvelle limite que nous obtenons

sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!

À partir de Python 3.5, l’exception est une erreur Récursion, dérivée de RuntimeError.

Récursion de la queue - Mauvaise pratique

Lorsque la seule chose renvoyée par une fonction est un appel récursif, on parle de récursion de queue.

Voici un exemple de compte à rebours écrit en utilisant la récursion de queue:

def countdown(n):
    if n == 0:
        print "Blastoff!"
    else:
        print n
        countdown(n-1)

Tout calcul pouvant être effectué à l'aide d'une itération peut également être effectué en utilisant la récursivité. Voici une version de find_max écrite en utilisant la récursion de la queue:

def find_max(seq, max_so_far):
    if not seq:
        return max_so_far
    if max_so_far < seq[0]:
        return find_max(seq[1:], seq[0])
    else:
        return find_max(seq[1:], max_so_far)

La récursion de la queue est considérée comme une mauvaise pratique en Python, car le compilateur Python ne gère pas l'optimisation des appels récursifs de queue. La solution récursive dans de tels cas utilise plus de ressources système que la solution itérative équivalente.

Optimisation de la récursion de la queue grâce à l'introspection de la pile

Par défaut, la pile de récurrence de Python ne peut pas dépasser 1000 images. Cela peut être changé en définissant le sys.setrecursionlimit(15000) qui est plus rapide cependant, cette méthode consomme plus de mémoire. Au lieu de cela, nous pouvons également résoudre le problème de la récursion de la queue en utilisant l'introspection de la pile.

#!/usr/bin/env python2.4
# This program shows off a python decorator which implements tail call optimization. It
# does this by throwing an exception if it is it's own grandparent, and catching such 
# exceptions to recall the stack.

import sys

class TailRecurseException:
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
  
This function fails if the decorated
function recurses in a non-tail context.
"""
      
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException, e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

Pour optimiser les fonctions récursives, nous pouvons utiliser le décorateur @tail_call_optimized pour appeler notre fonction. Voici quelques exemples de récurrence courants utilisant le décorateur décrit ci-dessus:

Exemple factoriel:

@tail_call_optimized
def factorial(n, acc=1):
  "calculate a factorial"
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

Exemple Fibonacci:

@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.