[Python] recursive generator

https://stackoverflow.com/questions/38254304/python-can-generators-be-recursive

Python: can generators be recursive?

 

앞서서 yield문을 이용하여 구현되는 generator에 대해 알아보았다.

그런데 이 generator를 recursive하게 구현하고 싶을 수가 있다.

먼저 list의 원소를 순서대로 print하는 function을

recursive하게 구현해보자.

def recursive_printer(_list):
    if not _list: # end the function when _list is empty
        return
    print(_list[0])
    recursive_printer(_list[1:])

if __name__ == "__main__":
    recursive_printer([8,6,4,2])

실행 결과는 다음과 같다.

8
6
4
2

이 function을 base로 list의 원소를 순서대로 반환하는 generator를 다음과 같이

작성해볼 수 있다.

def recursive_gen_1(_list):
    yield _list[0]
    recursive_gen_1(_list[1:])

if __name__ == "__main__":
   for k in recursive_gen_1([8,6,4,2]):
        print(k)

그러나 실행결과는 예상과 달랐다.

8

recursive_gen_1([8,6,4,2])을 호출하면서 generator-iterator에 대해 for loop 안에서 next()가 호출될 것이다.

그럼 recursive_gen_1()의 body의 첫 라인에 따라 iterator는 [8,6,4,2][0]인 8을 반환하고 이 data는 k에 할당된다.

그리고 여기서 generator의 실행은 '일시정지'된다.

 

이후 for loop의 print(k)가 실행되고

다음 loop가 돌면서 next()가 호출된다.

 

그리고 이 때 yield문의 다음 line인 recursive_gen_1(_list[1:])

즉 recursive_gen_1([6,4,2])가 호출된다.

 

여기서 처음 우리의 구현 의도는, recursive_gen_1([6,4,2])가 호출되면서 그 내부의 yield문이 다시 실행되는 것이었다.

하지만 여기서 문제는, recursive_gen_1([6,4,2])를 호출되면서 다시 generator-iterator가 생성되기는 하지만,

그 이후 아무 일도 일어나지 않는다는 것이었다.

 

즉, iterator를 생성하기만 해서는 [6,4,2]의 첫번째 원소인 6이 반환되는 일은 일어나지 않는다.

그렇다면 이 문제를 어떻게 해결해야 할까?

일반적인 generator의 형태를 다시 살펴보자.

def factors_gen(n):
    for k in range(1,n+1):
        if n%k == 0:
            yield k


def factors_gen2(n):
    k = 1
    while k*k < n:
        if n%k == 0:
            yield k
            yield n//k
        k += 1
    if k*k == n:
        yield k

yield문이 for-loop이나 while-loop 등의 반복문 안에 쓰인 것을 볼 수 있다.

즉, generator-iterator가 우리가 예상한대로 작동하려면,

next()호출로 body가 실행되어 yield문을 만난뒤 일시정지한 후

다음 next()호출로 그 다음 줄부터 다시 body가 실행될 때 다시 yield문을 만날 수 있도록

구현되어 있어야 한다.

 

다시 우리의 recursive_gen_1()을 보면, 최초의 yield문이 실행 된 뒤,

다음 next()호출 때  recursive_gen_1(_list[1:])이 호출되지만 그 뿐이라는 것을 볼 수 있다.

recursive_gen_1(_list[1:])는 generator-iterator를 생성하지만 이 iterator는

어딘가에 할당되지도 for-loop에서 쓰이지도 못했으므로 그 내부의 yield문 (우리가 6을 반환할 것이라 예상한 line)은

실행되지 못하는 것이다.

 

그렇다면 우리의 recursive_gen_1이 우리가 예상한 대로 작동하도록 보완하려면 어떻게 해야할까?

recursive하게 다시 generator를 호출하는 것은 마찬가지이지만,

이것을 for-loop에 넣어 body에서 생성된 iterator에 대해 next()가 호출되도록 하고

이것을 yield로 반환하도록 해야 한다.

 

def recursive_gen_2(_list):
    if not _list:
        return # end the iteration when _list is empty
    yield _list[0]
    for other in recursive_gen_2(_list[1:]):
        yield other

if __name__ == "__main__":
    for j in recursive_gen_2([8,6,4,2]):
        print(j)

 

실행결과는

8
6
4
2

 

실행과정을 분석해보자.

[main for-loop : 0]
recursive_gen_2([8,6,4,2]) iterator 생성
next(recursive_gen_2([8,6,4,2])) 호출
body 실행

yield [8,6,4,2][0] > 8 반환후 일시정지
8은 j에 할당 된 후 print(j)에 의해 출력


[main for-loop : 1]
next(recursive_gen_2([8,6,4,2])) 호출
body 실행
sub for-loop 진입 (for other in recursive_gen_2([6,4,2]))

    [sub for-loop : 0]
    recursive_gen_2([6,4,2]) sub iterator 생성
    next(recursive_gen_2([6,4,2])) 호출
    sub iterator body 실행

    yield [6,4,2][0] > 6 반환 후 일시정지

6은 other에 할당
yield other > 6 반환 후 일시정지
6은 j에 할당 된 후 print(j)에 의해 출력

[main for-loop : 2]
next(recursive_gen_2([8,6,4,2])) 호출
body 실행
sub for-loop resume

    [sub for-loop : 1]
    next(recursive_gen_2([6,4,2])) 호출
    sub-iterator body 실행
    sub-sub for-loop 진입 (for other in recursive_gen_2([4,2]))

        [sub-sub for-loop : 0]
        recursive_gen_2([4,2]) sub-sub iterator 생성
        next(recursive_gen_2([4,2])) 호출
        sub-sub iterator body 실행

        yield [4,2][0] > 4 반환 후 일시정지

    4는 other에 할당
    yield other > 4 반환 후 일시정지


4는 other에 할당
yield other > 4 반환 후 일시정지
4은 j에 할당 된 후 print(j)에 의해 출력

[main for-loop : 3]
next(recursive_gen_2([8,6,4,2])) 호출
body 실행
sub for-loop resume
    
    [sub for-loop : 2]
    next(recursive_gen_2([6,4,2])) 호출
    sub-iterator body 실행
    sub-sub for-loop resume (for other in recursive_gen_2([4,2]))

        
        [sub-sub for-loop : 1]
        next(recursive_gen_2([4,2])) 호출
        sub-sub iterator body 실행
        sub-sub-sub for loop 진입 (for other in recursive_gen_2([2]))

            [sub-sub-sub for-loop : 0]
            recursive_gen_2([2]) sub-sub-sub itereator 생성
            next(recursive_gen_2([2])) 호출
            sub-sub-sub iterator body 실행
            
            yield [2][0] > 2 반환 후 일시정지

        2 는 other에 할당
        yield other > 2 반환 후 일시정지

    2 는 other에 할당
    yield other > 2 반환 후 일시정지

2는 other에 할당
yield other > 2 반환 후 일시정지
2는 j에 할당 된 후 print(j)에 의해 출력

[main for-loop : 4]
next(recursive_gen_2([8,6,4,2])) 호출

...

                [sub-sub-sub-sub for loop : 0]
                recursive_gen_2([]) sub-sub-sub-sub itereator 생성
                next(recursive_gen_2([]))
                return 문을 만나 종료