CODEWITHSUNDEEP
pythonpython-3.xrecursion
Algorithmic Canary
Algorithmic Canary

Reputation: 742

Why does a function that returns itself max out recursion in python 3

Why does this code give the error: RuntimeError: maximum recursion depth exceeded during compilation? print_test never calls itself, hence I would think it isn't a recursive function.

def print_test():
    print("test")
    return print_test

print_test() #prints 'test'
print()

#a quick way of writing "print_test()()()()()()()()()()()()()..."
eval("print_test"+"()"*10000) #should print 'test' 10000 times

When I tested it, It worked in Python 2.7.7rc1 but gave the error in Python 3.3.5. Pdb give a short call stack, unlike the tall one that normally exists when exceeding maximum recursion depth.

Traceback (most recent call last):
  File "/usr/lib/python3.3/pdb.py", line 1662, in main
    pdb._runscript(mainpyfile)
  File "/usr/lib/python3.3/pdb.py", line 1543, in _runscript
    self.run(statement)
  File "/usr/lib/python3.3/bdb.py", line 405, in run
    exec(cmd, globals, locals)
  File "<string>", line 1, in <module>
  File "/home/beet/overflow.py", line 1, in <module>
    def print_test():

I am wondering this out of curiosity, and realize this would not be best programming practices.

Upvotes: 15

Views: 1153

Answers (2)

pepr
pepr

Reputation: 20762

The eval does the compilation. It can find that you want to go deeper with nested calls than sys.getrecursionlimit().

The recursion can be both direct (the function calls itself directly) or indirect (the function is called by another function which in turn was once called by this function). But when the call depth is greater than expected (1000 for the Python implementation at the time of writing), the call can be part of the indirect recursion that needs go even deeper to manifest itself to be recursive. In other words, if the maximum call depth is reached (and the depth is reasonable to think this way), it is fine to name it recursion that cannot be done.

The definitive answer can be found in sources... But I was just curious, so I did the following experiment. I tried to write the code that defines enough of distinct functions (with numbered identifiers) that call the next one -- except the last one that actually does not call the first one recursively.

def fn1():
    print('fn1() is going to call fn2()')
    fn2()

def fn2():
    print('fn2() is going to call fn3()')
    fn3()

def fn3():
    print('fn3() does not call anything.')

fn1()

The last line starts the nested calls and it prints.

fn1() is going to call fn2()
fn2() is going to call fn3()
fn3() does not call anything.

We can generate the source as a string, and then we can use the compile built-in function and then exec it:

#!python3
import textwrap

n = 1000
print('n =', n)

lst = []
for i in range(1, n+1):
    if i == n:
        fndef = textwrap.dedent('''\
            def fn{}():
                print('fn{}() does not call anything.')

            fn1()
            '''.format(i, i))
    else:
        fndef = textwrap.dedent('''\
            def fn{}():
                print('fn{}() is going to call fn{}()')
                fn{}()
            '''.format(i, i, i+1, i+1))

    if n <= 10:
        print(fndef)
    lst.append(fndef)

ast = compile('\n'.join(lst), '<string>', 'exec')
exec(ast)

Notice the n = 1000 at the beginning of the source. When executed and the stdout and stderr redirected to the files, I could observe:

n = 1000
fn1() is going to call fn2()
fn2() is going to call fn3()
fn3() is going to call fn4()
...
fn992() is going to call fn993()
fn993() is going to call fn994()
fn994() is going to call fn995()

Traceback (most recent call last):
  File "a.py", line 28, in <module>
    exec(ast)
  File "<string>", line 4000, in <module>
  File "<string>", line 3, in fn1
  File "<string>", line 7, in fn2
  File "<string>", line 11, in fn3
  ...
  File "<string>", line 3967, in fn992
  File "<string>", line 3971, in fn993
  File "<string>", line 3975, in fn994
  File "<string>", line 3978, in fn995
RuntimeError: maximum recursion depth exceeded

Conclusion: Python calls it recursion not only during eval when it is recursion but it was not executed, yet (as the question shows). Python may call it recursion even in the case when there is actually no recursion.

Better conclusion: Who cares when it is clear that the code could be a recursion or not, during compilation or in runtime. It would not work anyway :)

Upvotes: 2

Dair
Dair

Reputation: 16240

I believe this has to do with Issue #5765.

Apply a hard recursion limit in the compiler [as of 3.3]

Not 100% sure, but this code runs on 3.2.3:

def f():
    return f

eval("f" + "()" * 10000)

but fails on my 3.4.1 which leaves me to suspect this change caused it. If someone would confirm or deny this that would be pretty cool.

Upvotes: 9

Related Questions