Récursivité en utilisant le rendement

Question

Est-il possible de mélanger la récursion et l'instruction yield? Par exemple, un générateur de nombres infinis (en utilisant la récursion) ressemblerait à ceci :

def infinity(start):
    yield start
    # récursion ici ...

>>> it = infinity(1)
>>> next(it)
1
>>> next(it)
2

J'ai essayé :

def infinity(start):
    yield start
    infinity(start + 1)

et

def infinity(start):
    yield start
    yield infinity(start + 1)

Mais aucun d'entre eux n'a fait ce que je voulais, le premier s'est arrêté après avoir produit start et le second a produit start, puis le générateur et s'est arrêté.

NOTE: S'il vous plaît, je sais que vous pouvez le faire en utilisant une boucle while :

def infinity(start):
    while True:
        yield start
        start += 1

Je veux juste savoir si cela peut être fait de manière récursive.

Answer 1

Oui, vous pouvez le faire :

def infinity(start):
    yield start
    for x in infinity(start + 1):
        yield x

Cela générera une erreur une fois atteinte la profondeur maximale de récursion.

À partir de Python 3.3, vous pourrez utiliser

def infinity(start):
    yield start
    yield from infinity(start + 1)

Si vous appelez simplement votre fonction génératrice de manière récursive sans la parcourir ou faire un yield from, tout ce que vous ferez sera de créer un nouveau générateur sans exécuter le corps de la fonction ou générer quoi que ce soit.

Consultez PEP 380 pour plus de détails.

Answer 2

Il est parfois préférable d'utiliser une pile plutôt que la récursivité pour les générateurs. Il devrait être possible de réécrire une méthode récursive en utilisant une pile et une boucle while.

Voici un exemple d'une méthode récursive qui utilise un rappel et qui peut être réécrite en utilisant la logique de pile :

def parcourir_arbre(rappel):
    # Obtenir le nœud racine de quelque part.
    racine = obtenir_noeud_racine()
    def recursion(noeud):
        rappel(noeud)
        for enfant in noeud.get('children', []):
            recursion(enfant)
    recursion(racine)

La méthode ci-dessus parcourt un arbre de nœuds où chaque nœud a un tableau children qui peut contenir des nœuds enfants. À chaque nœud rencontré, le rappel est émis et le nœud actuel lui est transmis.

La méthode pourrait être utilisée de cette manière, en imprimant une propriété sur chaque nœud.

def rappel(noeud):
    print(noeud['id'])
parcourir_arbre(rappel)

Utiliser une pile à la place et écrire la méthode de traversal comme un générateur

# Une alternative basée sur une pile à la méthode traverse_tree ci-dessus.
def iter_noeuds():
    pile = [obtenir_noeud_racine()]
    while pile:
        noeud = pile.pop()
        yield noeud
        for enfant in reversed(noeud.get('children', [])):
            pile.append(enfant)

(Notez que si vous voulez le même ordre de traversal qu'initialement, vous devez inverser l'ordre des enfants car le premier enfant ajouté à la pile sera le dernier à être retiré.)

Maintenant, vous pouvez obtenir le même comportement que traverse_tree ci-dessus, mais avec un générateur :

for noeud in iter_noeuds():
    print(noeud['id'])

Ce n'est pas une solution universelle mais pour certains générateurs, vous pourriez obtenir un bon résultat en substituant le traitement de la pile à la récursivité.

Answer 3

def lprint(a):
    if isinstance(a, list):
        for i in a:
            yield from lprint(i)
    else:
        yield a

b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
    print(i)

Answer 4

Donc essentiellement, vous avez juste besoin d'ajouter une boucle for à l'endroit où vous devez appeler votre fonction de manière récursive. Cela s'applique pour Python 2.7.