My question was: Is it possible to bypass the recursion limit with generators and yield from?
Answer: You can prevent the
Here a function to generate a nested list:
Now a normal function to traverse the deep list.
complicated code.
This means, the interpreter was not able to get finally the str element. The recursion limit was hit before.
Now let's try it with the generator version:
I guess the recursion limit is still thrown, but goes in silence away.
Apply the generator twice gives:
Instead of using
This also faster.
Answer: You can prevent the
RecursionError
, but you are still limited in recursion.Here a function to generate a nested list:
def construct_deep_list(n): x = y = [] for _ in range(n): x.append([]) x = x[0] x.append('Secret') return y
construct_deep_list(10)
Output:[[[[[[[[[[['Secret']]]]]]]]]]]
Now getting the recursionlimit, generating the deep_list and printing it to console.import sys deep_list = construct_deep_list(sys.getrecursionlimit()) print(deep_list)Then you get this error:
Error:RecursionError Traceback (most recent call last)
<ipython-input-158-1a3df04d5171> in <module>
1 deep_list = construct_deep_list(sys.getrecursionlimit())
----> 2 print(deep_list)
RecursionError: maximum recursion depth exceeded while getting the repr of an object
Now a normal function to traverse the deep list.
str
and bytes
are not allowed to prevent morecomplicated code.
def test_recursion(iterable): try: iterator = iter(iterable) except TypeError: return iterable else: while True: try: element = next(iterator) if isinstance(element, (str, bytes)): raise ValueError('str or bytes are not allowed') return test_recursion(element) except StopIteration: breakTesting the functions:
result = test_recursion([[True]]) print(result)It works:
Output:True
Now let's try it with the deep_list:result2 = test_recursion(deep_list)
Error:RecursionError Traceback (most recent call last)
<ipython-input-197-311c4b04144f> in <module>
----> 1 result2 = test_recursion(deep_list)
<ipython-input-190-48a43684de23> in test_recursion(iterable)
13 if isinstance(element, (str, bytes)):
14 raise ValueError('str or bytes are not allowed')
---> 15 return test_recursion(element)
16 except StopIteration:
17 break
... last 1 frames repeated, from the frame below ...
<ipython-input-190-48a43684de23> in test_recursion(iterable)
13 if isinstance(element, (str, bytes)):
14 raise ValueError('str or bytes are not allowed')
---> 15 return test_recursion(element)
16 except StopIteration:
17 break
RecursionError: maximum recursion depth exceeded in __instancecheck__
The deep_list has one str inside. But we got the RecursionError and not the ValueError.This means, the interpreter was not able to get finally the str element. The recursion limit was hit before.
Now let's try it with the generator version:
def deep_iter(iterable): for element in iterable: try: yield from deep_iter(element) except: yield element
result3 = list(deep_iter(deep_list)) print(result3)
Output:[[[[[[[[[[[[[[[[[[['Secret']]]]]]]]]]]]]]]]]]]
Conclusion: Generators can simplify your code. But I still do not know why the yield from
does not hit the recursion limit.I guess the recursion limit is still thrown, but goes in silence away.
Apply the generator twice gives:
result4 = list(deep_iter(deep_iter(deep_list))) print(result4)
Output:['Secret']
Extended generator, which does not iterate over str
and bytes
:def deep_iter2(iterable, ignore=(str, bytes)): for element in iterable: if isinstance(element, ignore): yield element continue try: yield from deep_iter2(element) except: yield element
print(list(deep_iter2(deep_iter2(deep_list))))
Output:['Secret']
I'm not sure if it's usable in production code. But usually you should not have deep nested data structures in production code (hopefully).Instead of using
yield from
, I use the deque in the final version.This also faster.
from collections import deque def deep_iter3(iterable, ignore=(str, bytes)): heap = deque([iterable]) while heap: element = heap.popleft() if isinstance(element, ignore): yield element continue try: sub_heap = [] for sub_element in element: sub_heap.append(sub_element) except TypeError: yield element else: heap.extendleft(reversed(sub_heap))
list(deep_iter3([1,2, ['test'], (3,1),4, deep_list]))
Output:[1, 2, 'test', 3, 1, 4, 'Secret']
Some benchmarks:Output:In [83]: %timeit list(deep_iter3([1,2, ['test'], (3,1),4, deep_list]))
1.26 ms ± 8.92 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [84]: %timeit list(deep_iter2([1,2, ['test'], (3,1),4, deep_list]))
17.9 ms ± 33.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [85]: %timeit list(deep_iter([1,2, ['test'], (3,1),4, deep_list]))
85.6 ms ± 167 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Almost dead, but too lazy to die: https://sourceserver.info
All humans together. We don't need politicians!
All humans together. We don't need politicians!