Les générateurs peuvent-ils être récursifs?

Question

J'ai naïvement essayé de créer un générateur récursif. N'a pas fonctionné C'est ce que j'ai fait:

 def recursive_generator(lis):
    yield lis[0]
    recursive_generator(lis[1:])

for k in recursive_generator([6,3,9,1]):
    print(k)
 

Tout ce que j'ai, c'est le premier élément 6 .

Existe-t-il un moyen de faire fonctionner ce code? Transférer essentiellement la commande yield au niveau supérieur dans un schéma de récurrence?

Answer 1

Essaye ça:

 def recursive_generator(lis):
    yield lis[0]
    yield from recursive_generator(lis[1:])

for k in recursive_generator([6,3,9,1]):
    print(k)
 

Je dois signaler que cela ne fonctionne pas à cause d'un bogue dans votre fonction. Il devrait probablement inclure un contrôle que lis n'est pas vide, comme indiqué ci-dessous:

 def recursive_generator(lis):
    if lis:
        yield lis[0]
        yield from recursive_generator(lis[1:])
 

Si vous utilisez Python 2.7 et que vous n'avez pas yield from , consultez cette question.

Answer 2

Pourquoi votre code n'a pas faire le travail

Dans votre code, la fonction de générateur:

1. retourne (rendements), la première valeur de la liste
2. puis il crée un nouvel itérateur objet d'appeler la même fonction de générateur, le passage d'une tranche de la liste, il
3. et puis s'arrête

La deuxième instance de l'itérateur, l'un de manière récursive créé, est de ne jamais être itéré. C'est pourquoi, que vous avez reçu le premier élément de la liste.

Un générateur de fonction est utile pour créer automatiquement un itérateur objet (un objet qui implémente l' itérateur protocole), mais alors vous avez besoin pour effectuer une itération sur elle: soit manuellement à l'appel de la next() méthode sur l'objet ou par le biais d'une boucle de déclaration qui va automatiquement utiliser l'itérateur protocole.

Oui, peut-on appeler récursivement un générateur?

La réponse est oui. Maintenant, revenons à votre code, si vous avez vraiment envie de le faire avec un générateur de fonction, je suppose que vous pourriez essayer:

def recursive_generator(some_list):
    """
    Return some_list items, one at a time, recursively iterating over a slice of it... 
    """
    if len(some_list)>1:
    # some_list has more than one item, so iterate over it
        for i in recursive_generator(some_list[1:]):
            # recursively call this generator function to iterate over a slice of some_list.
            # return one item from the list.
            yield i
        else:
            # the iterator returned StopIteration, so the for loop is done.
            # to finish, return the only value not included in the slice we just iterated on.
            yield some_list[0]
    else:
        # some_list has only one item, no need to iterate on it.
        # just return the item.
        yield some_list[0]

some_list = [6,3,9,1]
for k in recursive_generator(some_list):
    print(k)

Remarque: les articles sont retournés dans l'ordre inverse, de sorte que vous pouvez utiliser some_list.reverse() avant d'appeler le générateur de la première fois.

La chose importante à noter dans cet exemple est: le générateur de fonction récursive s'appelle elle-même dans un de boucle, qui voit d'un itérateur, et utilise automatiquement l'itération protocole sur elle, alors elle se des valeurs.

Cela fonctionne, mais je pense que ce n'est vraiment pas utile. Nous sommes à l'aide d'un générateur de fonction pour parcourir une liste et d'obtenir juste les articles un à un, mais... la liste est un objet iterable lui-même, donc pas besoin pour les générateurs! Bien sûr, je comprends, c'est juste un exemple, peut-être il y a des applications utiles de cette idée.

Un autre exemple

Recyclons l'exemple précédent (par paresse). Disons que nous avons besoin d'imprimer les éléments dans une liste, en ajoutant à chaque article le nombre de précédents articles (juste un hasard, pas forcément utile).

Le code serait:

def recursive_generator(some_list):
    """
    Return some_list items, one at a time, recursively iterating over a slice of it...
    and adding to every item the count of previous items in the list
    """
    if len(some_list)>1:
    # some_list has more than one item, so iterate over it
        for i in recursive_generator(some_list[1:]):
            # recursively call this generator function to iterate over a slice of some_list.
            # return one item from the list, but add 1 first. 
            # Every recursive iteration will add 1, so we basically add the count of iterations.
            yield i + 1
        else:
            # the iterator returned StopIteration, so the for loop is done.
            # to finish, return the only value not included in the slice we just iterated on.
            yield some_list[0]
    else:
        # some_list has only one item, no need to iterate on it.
        # just return the item.
        yield some_list[0]

some_list = [6,3,9,1]
for k in recursive_generator(some_list):
    print(k)

Maintenant, comme vous pouvez le voir, le générateur de fonction est en train de faire quelque chose avant de retourner les éléments de la liste ET l'utilisation de la récursivité commence à faire sens. Encore, juste un exemple stupide, mais vous obtenez l'idée.

Remarque: bien sûr, dans ce stupide exemple, la liste devrait contenir que des chiffres. Si vous voulez vraiment aller de l'essayer et de le casser, il suffit de mettre dans une chaîne de caractères dans some_list et avoir du plaisir. Encore une fois, ce n'est qu'un exemple, pas de production de code!

Answer 3

Les générateurs récursifs sont utiles pour traverser des structures non linéaires. Par exemple, supposons qu'un arbre binaire soit Aucun ou un tuple de valeur, arbre de gauche, arbre de droite. Un générateur récursif est le moyen le plus simple de visiter tous les nœuds. Exemple:

 tree = (0, (1, None, (2, (3, None, None), (4, (5, None, None), None))),
        (6, None, (7, (8, (9, None, None), None), None)))

def visit(tree):  # 
    if tree is not None:
        try:
            value, left, right = tree
        except ValueError:  # wrong number to unpack
            print("Bad tree:", tree)
        else:  # The following is one of 3 possible orders.
            yield from visit(left)
            yield value  # Put this first or last for different orders.
            yield from visit(right)

print(list(visit(tree)))

# prints nodes in the correct order for 'yield value' in the middle.
# [1, 3, 2, 5, 4, 0, 6, 9, 8, 7]
 

Éditer: remplacez if tree par if tree is not None pour intercepter d'autres valeurs fausses sous forme d'erreurs.

Answer 4

Une fonction du générateur doit générer une exception StopIteration fin. Pour le cas récursif, d'autres exceptions (par exemple, IndexError ) sont levées avant StopIteration , nous l'ajoutons donc manuellement.

 def recursive_generator(lis):
    if not lis: raise StopIteration
    yield lis[0]
    yield from recursive_generator(lis[1:])

for k in recursive_generator([6, 3, 9, 1]):
    print(k)
 

---

 def recursive_generator(lis):
    if not lis: raise StopIteration
    yield lis.pop(0)
    yield from recursive_generator(lis)

for k in recursive_generator([6, 3, 9, 1]):
    print(k)
 

Notez que for boucle attrapera StopIteration exception. Plus à ce sujet ici