생성기는 재귀적일 수 있습니까?
순진하게 재귀 생성기를 만들려고했습니다. 작동하지 않았습니다. 이것이 내가 한 일입니다.
def recursive_generator(lis):
yield lis[0]
recursive_generator(lis[1:])
for k in recursive_generator([6,3,9,1]):
print(k)
내가 얻은 것은 첫 번째 항목뿐이었습니다 6
.
그러한 코드를 작동시키는 방법이 있습니까? 본질적 yield
으로 재귀 체계에서 명령을 위 수준으로 전송 합니까?
이 시도:
def recursive_generator(lis):
yield lis[0]
yield from recursive_generator(lis[1:])
for k in recursive_generator([6,3,9,1]):
print(k)
함수의 버그로 인해 작동하지 않는다는 점을 지적해야합니다. lis
아래와 같이 비어 있지 않은 수표를 포함해야 합니다.
def recursive_generator(lis):
if lis:
yield lis[0]
yield from recursive_generator(lis[1:])
경우에 당신은 파이썬 2.7에 있고이없는 yield from
, 이 질문을 확인하십시오.
코드가 제대로 작동하지 않는 이유
코드에서 생성기 함수 :
- 목록의 첫 번째 값을 반환 (수율)합니다.
- 그런 다음 동일한 생성기 함수를 호출 하는 새 반복기 객체를 생성하여 목록 조각을 전달합니다.
- 그리고 중지
반복기의 두 번째 인스턴스 인 재귀 적으로 생성 된 인스턴스는 반복되지 않습니다. 그래서 목록의 첫 번째 항목 만 얻었습니다.
생성기 함수는 반복기 객체 ( 반복기 프로토콜 을 구현하는 객체)를 자동으로 생성하는 데 유용 하지만 객체에 대한 메서드를 수동으로 호출 next()
하거나 자동으로 사용하는 루프 문을 통해 반복해야합니다. 반복자 프로토콜.
그렇다면 재귀 적으로 생성기를 호출 할 수 있습니까?
대답은 ' 예' 입니다. 당신이 경우 지금 다시 코드, 정말 발전기 기능이 작업을 수행 할 수, 당신이 시도 할 수 같아요
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)
참고 : 항목은 역순으로 반환되므로 some_list.reverse()
생성기를 처음 호출하기 전에 사용 하는 것이 좋습니다.
이 예제에서 주목해야 할 중요한 사항 은 생성기 함수가 반복기를 보고 자동으로 반복 프로토콜을 사용 하는 for 루프 에서 자신을 재귀 적으로 호출 하므로 실제로 값을 가져옵니다.
이것은 작동하지만 이것은 실제로 유용하지 않다고 생각합니다 . 우리는 생성기 함수를 사용하여 목록을 반복하고 한 번에 하나씩 항목을 가져 오지만 ... 목록 자체는 반복 가능하므로 생성기가 필요하지 않습니다! 물론 이해합니다. 이것은 단지 예일뿐입니다. 아마도이 아이디어의 유용한 응용이있을 수 있습니다.
다른 예시
이전 예제를 재활용 해 보겠습니다 (게으름을 위해). 모든 항목에 이전 항목 수를 추가하여 목록의 항목을 인쇄해야한다고 가정 해 보겠습니다 (반드시 유용하지는 않음).
코드는 다음과 같습니다.
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)
이제 보시다시피 제너레이터 함수는 목록 항목을 반환하기 전에 실제로 무언가를 수행하고 있으며 재귀 사용이 이해되기 시작합니다. 그래도 어리석은 예이지만 아이디어를 얻습니다.
Note: off course, in this stupid example the list is expected to contain only numbers. If you really want to go try and break it, just put in a string in some_list and have fun. Again, this is only an example, not production code!
Recursive generators are useful for traversing non-linear structures. For example, let a binary tree be either None or a tuple of value, left tree, right tree. A recursive generator is the easiest way to visit all nodes. Example:
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]
Edit: replace if tree
with if tree is not None
to catch other false values as errors.
Edit 2: about putting the recursive calls in the try: clause (comment by @jpmc26).
For bad nodes, the code above just logs the ValueError and continues. If, for instance, (9,None,None)
is replaced by (9,None)
, the output is
Bad tree: (9, None)
[1, 3, 2, 5, 4, 0, 6, 8, 7]
More typical would be to reraise after logging, making the output be
Bad tree: (9, None)
Traceback (most recent call last):
File "F:\Python\a\tem4.py", line 16, in <module>
print(list(visit(tree)))
File "F:\Python\a\tem4.py", line 14, in visit
yield from visit(right)
File "F:\Python\a\tem4.py", line 14, in visit
yield from visit(right)
File "F:\Python\a\tem4.py", line 12, in visit
yield from visit(left)
File "F:\Python\a\tem4.py", line 12, in visit
yield from visit(left)
File "F:\Python\a\tem4.py", line 7, in visit
value, left, right = tree
ValueError: not enough values to unpack (expected 3, got 2)
The traceback gives the path from the root to the bad node. One could wrap the original visit(tree)
call to reduce the traceback to the path: (root, right, right, left, left).
If the recursive calls are included in the try: clause, the error is recaught, relogged, and reraised at each level of the tree.
Bad tree: (9, None)
Bad tree: (8, (9, None), None)
Bad tree: (7, (8, (9, None), None), None)
Bad tree: (6, None, (7, (8, (9, None), None), None))
Bad tree: (0, (1, None, (2, (3, None, None), (4, (5, None, None), None))), (6, None, (7, (8, (9, None), None), None)))
Traceback (most recent call last):
... # same as before
The multiple logging reports are likely more noise than help. If one wants the path to the bad node, it might be easiest to wrap each recursive call in its own try: clause and raise a new ValueError at each level, with the contructed path so far.
Conclusion: if one is not using an exception for flow control (as may be done with IndexError, for instance) the presence and placements of try: statements depends on the error reporting one wants.
Up to Python 3.4, a generator function used to have to raise StopIteration
exception when it is done. For the recursive case other exceptions (e.g. IndexError
) are raised earlier than StopIteration
, therefore we add it manually.
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)
Note that for
loop will catch StopIteration
exception. More about this here
Yes you can have recursive generators. However, they suffer from the same recursion depth limit as other recursive functions.
def recurse(x):
yield x
yield from recurse(x)
for (i, x) in enumerate(recurse(5)):
print(i, x)
This loop gets to about 3000 (for me) before crashing.
However, with some trickery, you can create a function that feeds a generator to itself. This allows you to write generators like they are recursive but are not: https://gist.github.com/3noch/7969f416d403ba3a54a788b113c204ce
ReferenceURL : https://stackoverflow.com/questions/38254304/can-generators-be-recursive
'Program Tip' 카테고리의 다른 글
belongsToMany 관계가 존재하는지 확인-Laravel (0) | 2020.12.26 |
---|---|
pandas와 인덱스의 데이터 프레임 병합 (0) | 2020.12.15 |
Cloud Functions와 Firebase Functions의 차이점은 무엇인가요? (0) | 2020.12.15 |
axios로 기본 인증을 보내는 방법 (0) | 2020.12.15 |
MySQL의 각 그룹에 대한 첫 번째 행을 선택하는 방법은 무엇입니까? (0) | 2020.12.15 |