[Python-Dev] Proper tail recursion (original) (raw)

Michael Chermside mcherm at mcherm.com
Thu Jul 15 23:38:20 CEST 2004

I wrote:

The recursion limit (the value of it anyhow) is an implementation detail.

Martin replies:

No, it is not. In standard Python, the program

def rec(n): rec(n-1) n=1 while 1: try: rec(n) except RuntimeError: break print "The recursion limit is", n will terminate. In the modified Python, it will not terminate. It is a change in behaviour, and thus a language feature.

First, I'm going to make a slight modification to your program, since I want a version that actually does display the recursion limit. I tried the following program instead:

>>> def rec(n):
...     print n
...     rec(n+1)
...
>>> rec(1)

Running this in Jython 2.1 (a well-known implementation of the Python language) produced the numbers from 1 to 888, then immediately exited.

Running it on CPython 2.3 produced the numbers from 1 to 999, then a traceback that looked like this: Traceback (most recent call last): File "", line 1, in ? File "", line 3, in rec File "", line 3, in rec File "", line 3, in rec File "", line 3, in rec File "", line 3, in rec File "", line 3, in rec [... etc for a total of about 1000 lines ...] File "", line 3, in rec File "", line 3, in rec File "", line 3, in rec File "", line 3, in rec RuntimeError: maximum recursion depth exceeded

It then returned me to the interactive prompt.

I presume that since the behavior was different, CPython must not actually be a correct implementation of the Python language, right?

Not-all-differences-are-language-differences lly yours,

Michael Chermside

More information about the Python-Dev mailing list