Bottom Page

• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 Cheat against recursion limit DeaD_EyE Giant Foot Posts: 963 Threads: 5 Joined: May 2017 Reputation: 82 Likes received: 198 #1 Feb-10-2019, 09:57 AM (This post was last modified: Feb-10-2019, 10:16 AM by DeaD_EyE. Edited 7 times in total. Edit Reason: fixed errors, added deep_iter2 ) My question was: Is it possible to bypass the recursion limit with generators and yield from? 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) in 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 more complicated 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: break ```Testing 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) in ----> 1 result2 = test_recursion(deep_list) 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 ... 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) `````` My code examples are always for Python >=3.6.0 Almost dead, but too lazy to die: https://sourceserver.info All humans together. We don't need politicians! perfringo Verb Conjugator Posts: 748 Threads: 1 Joined: Jun 2018 Reputation: 69 Likes received: 152 #2 Feb-10-2019, 10:03 AM On topic of Python recursion: A thing I learned about Python recursion Quote:In Python 3, all comprehensions (and in Python 2 all except list comprehensions) are actually compiled as nested functions. Executing the generator comprehension calls that hidden nested function, using up an extra stack frame. I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy Life of Brian: Conjugate the verb, "to go" ! DeaD_EyE Giant Foot Posts: 963 Threads: 5 Joined: May 2017 Reputation: 82 Likes received: 198 #3 Feb-10-2019, 10:44 AM Interesting article. I like the pragmatic talks from Ned Batchelder. I added a comment to the article with a link to this thread. My code examples are always for Python >=3.6.0 Almost dead, but too lazy to die: https://sourceserver.info All humans together. We don't need politicians! « Next Oldest | Next Newest »

Top Page

 Possibly Related Threads... Thread Author Replies Views Last Post recursion function (python beginner) everafter 3 107 Aug-19-2019, 07:24 AM Last Post: buran Restrict / Limit variable size mln4python 4 137 Aug-13-2019, 07:17 AM Last Post: mln4python Recursion, with "some_dict={}" function parameter. MvGulik 3 121 Aug-02-2019, 01:34 PM Last Post: MvGulik Pyinstaller Maximum recursion bug scales11 7 1,118 Apr-10-2019, 07:06 PM Last Post: scales11 RecursionError: maximum recursion depth exceeded in comparison ? leoahum 11 1,391 Mar-18-2019, 01:53 PM Last Post: leoahum The Empty List Blocks Recursion leoahum 6 305 Mar-05-2019, 06:55 PM Last Post: leoahum function call in recursion moong 2 318 Feb-17-2019, 09:48 AM Last Post: moong How recursion function is applied? dukoolsharma 2 368 Dec-06-2018, 12:35 PM Last Post: himanibansal fibonacci ***Time limit exceeded*** frequency 18 1,121 Nov-29-2018, 09:03 PM Last Post: frequency 'Time Limit Exceeded' Problem bkpee3 2 603 Nov-14-2018, 03:51 AM Last Post: bkpee3

Forum Jump:

Users browsing this thread: 1 Guest(s)