[python] yield를 사용한 재귀

Program / 글쓴이

재귀와 yield문 을 혼합하는 방법이 있습니까? 예를 들어 무한 수 생성기 (재귀 사용)는 다음과 같습니다.

def infinity(start):
    yield start
    # recursion here ...

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

나는 시도했다 :

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

과

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

그러나 그들 중 누구도 내가 원하는 것을하지 않았습니다. 첫 번째는 항복 start하고 두 번째는 항복 start한 다음 발전기를 멈췄습니다.

참고 : while 루프를 사용하여이 작업을 수행 할 수 있다는 것을 알고 있습니다.

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

나는 이것이 재귀 적으로 수행 될 수 있는지 알고 싶습니다.

답변

예, 다음과 같이 할 수 있습니다.

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

그러나 최대 재귀 깊이에 도달하면 오류가 발생합니다.

Python 3.3부터 다음을 사용할 수 있습니다.

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

생성기 함수를 반복하거나 yield from-ing 하지 않고 재귀 적으로 호출 하면 실제로 함수 본문을 실행하거나 아무것도 생성하지 않고 새 생성기를 빌드하기 만하면 됩니다.

자세한 내용은 PEP 380 을 참조 하십시오.

답변

경우에 따라 생성기에 재귀 대신 스택을 사용하는 것이 더 나을 수 있습니다. 스택과 while 루프를 사용하여 재귀 메서드를 다시 작성할 수 있어야합니다.

다음은 콜백을 사용하고 스택 로직을 사용하여 재 작성할 수있는 재귀 메서드의 예입니다.

def traverse_tree(callback):
    # Get the root node from somewhere.
    root = get_root_node()
    def recurse(node):
        callback(node)
        for child in node.get('children', []):
            recurse(child)
    recurse(root)

위의 방법은 각 노드에 children자식 노드를 포함 할 수 있는 배열이 있는 노드 트리를 순회합니다 . 각 노드가 발견되면 콜백이 발행되고 현재 노드가 전달됩니다.

이 방법은 각 노드에서 일부 속성을 인쇄하는 방식으로 사용할 수 있습니다.

def callback(node):
    print(node['id'])
traverse_tree(callback)

대신 스택을 사용하고 순회 메소드를 생성기로 작성하십시오.

# A stack-based alternative to the traverse_tree method above.
def iternodes():
    stack = [get_root_node()]
    while stack:
        node = stack.pop()
        yield node
        for child in reversed(node.get('children', [])):
            stack.append(child)

(원래와 동일한 순회 순서를 원할 경우 스택에 추가 된 첫 번째 자식이 마지막으로 팝되기 때문에 자식의 순서를 반대로해야합니다.)

이제 traverse_tree위와 동일한 동작을 얻을 수 있지만 생성기를 사용하면됩니다.

for node in iternodes():
    print(node['id'])

이것은 하나의 크기에 맞는 솔루션은 아니지만 일부 생성기의 경우 재귀 대신 스택 처리를 대체하는 멋진 결과를 얻을 수 있습니다.

답변

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)

답변

따라서 기본적으로 함수를 재귀 적으로 호출해야하는 곳에 for 루프를 추가하면됩니다 . 이것은 Python 2.7에 적용됩니다.

답변