Recursion limit in Python when indexing

Question

I was fooling around with the recursion limit in Python, which may be dynamically altered using sys.setrecursionlimit(limit). The code below demonstrates that the integer limit exactly corresponds to the maximum depth allowed for recursive function calls.

For recursive indexing using [], the same recursion limit seems to apply, but apparently with a factor of 3, meaning that I can index three times deeper than I can call:

The above plot is generated by the code below.

import itertools, sys
import numpy as np
import matplotlib.pyplot as plt

limits = np.arange(10, 500, 100)

# Find max depth of recursive calls
maxdepth = []
for limit in limits:
    sys.setrecursionlimit(limit)
    try:
        n = [0]
        def fun(n=n):
            n[0] += 1
            fun()
        fun()
    except RecursionError:
        maxdepth.append(n[0])
a, b = np.polyfit(limits, maxdepth, 1)
plt.plot(limits, maxdepth, '*')
plt.plot(limits, a*limits + b, '-', label='call')
plt.text(np.mean(limits), a*np.mean(limits) + b, f'slope = {a:.2f}')

# Find max depth of getitem
maxdepth = []
n = 0
l = []; l.append(l)
for limit in limits:
    sys.setrecursionlimit(limit)
    for n in itertools.count(n):
        try:
            eval('l' + '[-1]'*n)
        except RecursionError:
            break
    maxdepth.append(n)
a, b = np.polyfit(limits, maxdepth, 1)
plt.plot(limits, maxdepth, '*')
plt.plot(limits, a*limits + b, '-', label='getitem')
plt.text(np.mean(limits), a*np.mean(limits) + b, f'slope = {a:.2f}')

plt.xlabel('Recursion limit')
plt.ylabel('Max depth')
plt.legend()
plt.savefig('test.png')

To test the recursive indexing I append a list l to itself and construct a long literal [-1][-1][-1]... which I then evaluate on l dynamically.

Question: Explain this factor of 3.

In my case I get a factor around 0.58 for call and 1.75 for getitem, which makes even less sense... 1.75/0.58 is still about 3 though. — Julien
– Julien, Commented Jan 29, 2019 at 0:02
That was for small depth. Gets actually closer to 1 and 3 as I increase the limit. I still stay below 1 for call though when it should intuitively be exactly 1 for all cases. Interested to know what hidden mechanism is at work here... — Julien
– Julien, Commented Jan 29, 2019 at 0:11
Strange. I found 1.00 and 3.00 on both Python 3.7 and 3.5, 64bit Linux Mint. I guess this could be platform dependent? — jmd_dk
– jmd_dk, Commented Jan 29, 2019 at 0:22
@Julien: Some of the limit is expended on the test code and provides a constant offset. — Davis Herring
– Davis Herring, Commented Jan 29, 2019 at 3:23

Davis Herring · Accepted Answer · 2019-01-31 07:44:15Z

2

There’s no recursion in l[-1][-1]…—it compiles to “push l; replace top of stack with its last element; replace…”. Your RecursionError is from compiling the long string.

There is very literally a factor of 3 used to approximate the stack usage of the byte-compiler vs. the interpreter proper. (Python 2 has no such limit and just crashes on such expressions.)

answered Jan 31, 2019 at 7:44

Davis Herring

42k4 gold badges58 silver badges91 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursion limit in Python when indexing

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related